2022.05.09(LC

①确定状态：dp[i] 为到达第 i 个台阶的方法总数

②转移方程：dp[i] = dp[i - 1] + dp[i - 2];

③初始条件和边界情况：dp[1] = 1;  dp[2] = 2;

④计算顺序：因为 dp[i] 由 dp[i-1] 和 dp[i-2]推出，所以从前往后遍历

class Solution {
    public int climbStairs(int n) {
        //第 n 个台阶只能从第 n - 2 或第 n - 1 个台阶爬上来，
        //到第 n - 2个台阶的走法 ＋ 到第 n - 1 个台阶的走法 = 到第 n 个台阶的走法
        if (n <= 2) return n;
        //确定状态
        int[] dp = new int[n + 1];
        //初始条件
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            //状态转移方程以及计算顺序
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

--滚动数组实现

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}