70 爬楼梯

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

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

五部曲可以简化为三部曲，

1. 定义dp含义和下标含义
2. 找递推公式（利用规律去寻找？）
3. dp数组如何初始化和递推的循环

首先定义dp数组的含义， dp数组是第i阶楼梯到楼顶可以有多少种方法。i是多少阶楼梯到楼顶。

其次递推公式： 假设现在我们总共有i个台阶，那么到达台阶i可以由i-1阶加一步到达或者i-2阶加两步到达。 所以dp[i] = dp[i-1] + dp[i-2]

最后dp数组初始化和递推循环 初始化给了两个dp[2] = 2, dp[3] = 3, 首先我们求解出dp[1], dp[1]表示有一个阶梯到楼顶，那么只有一种方法，所以dp[1] = 1 递推循环从i=1开始，到i=n结束。

var climbStairs2 = function(n) {
    var dp = [undefined, 1, 2, 3]
    for(let i=4;i<=n;i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

这里我们还可以做程序上的优化，省掉dp数组，因为当前dp[i]只和前两个状态有关系。

var climbStairs3 = function(n) {
    var pre = 1
    var curr = 2
    if (n <=2) {
        return n
    }
    for(let i=3;i<=n;i++) {
        const newCurr = pre + curr
        pre = curr
        curr = newCurr
    }
    return curr
}