题目链接 => 戳这里

题目截图

解析

动态规划四步走：
1.问题拆解：

我们到达第n个楼梯可以从第n-1个或者第n-2个楼梯到达，因此对第N个问题的求解就变成了对第n-1个问题和第n-2个问题的求解；

2.状态定义：

从起点到达第n个楼梯的方法总数=从起点到达第n-1个楼梯的方法总数+从起点到达第n-2个楼梯的方法总数；

3.递推方程

dp[n] = dp[n-2] + dp[n-1];

4.实现

在实现过程，除了关键性的递推方程推导，还需要注意状态的初始化；在这道题里面，我们需要独立定义当n=0,1,2时的状态值；

题解

class Solution {
    public int climbStairs(int n) {
        // 无需推导状态值可直接返回
        if (n < 3) {
            return n;
        }
        // 这是dp的基本操作，定义一个数组存储中间状态值
        int[] dp = new int[n+1];
        // 定义基本状态值
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

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