1.1. 题目

1.1.1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

1.1.2. 题解:

• 爬楼梯,每次可以一步或者两步,n表示总阶数
• 题目好理解

1.1.3. 思路:

• 第一反应就是用动态规划,不过我不会写,这是我学习动态规划的第一个例子
  • 动态规划其实就是从结果往前推导,已知结果的情况下,求得可能性
• 其实不知道动态规划的,第一反应还是暴力解法
  • 暴力循环就是 有可能走一步可能走一步
  • 第一步要么走一步或者走两步
  • 第二步也是要么走一步后者走两步
  • 走到走满n阶,就不走了..
  • 把所有的可能性加起来

1.1.4. 代码:

// 动态规划
func climbStairs(n int) int {
    if n == 1 {
        return 1
    }

    dp := make([]int,n+1)
    dp[1] = 1
    dp[2] = 2

    for i:=3;i<=n;i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

// 暴力解法
func climbStairs2(i,n int) int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    return climbStairs2(i+1,n) + climbStairs2(i+2,n)
}

代码