Cocolib爬楼梯
TIP
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路
dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
动规五部曲
- 确定dp数组以及下标的含义：
i表示爬的总台阶数，dp[i]表示爬到i阶台阶一共有几种方法 - 确定递推公式：
dp[i] = dp[i-1]+dp[i-2] - dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
js
var climbStairs = function(n) {
let dp = []
dp[1] = 1
dp[2] = 2
for(let i=3;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2]
}
return dp[n]
};