题目链接 => 戳这里
题目截图
解析
动态规划四步走：
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];
}
}
