参考文章：代码随想录https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
一、题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶提示：
- 1 <= n <= 45
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/climbing-stairs
二、题解
只要想到要到达第 n 阶台阶，要么是从第 n-1 阶跨一步，要么是从第 n-2 阶跨两步，便可推出递推公式
再用动态规划五部曲详细分析一下：
- 确定 dp 数组以及下标的含义
dp[i]： 爬到第 i 层楼梯，有 dp[i] 种方法
- 确定递推公式
从 dp[i] 的定义可以看出，dp[i] 可以有两个方向推出来。
首先是 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 数组如何初始化
本题考虑 dp[0] = 1 还是 2 其实没有意义，因为都能解释的通，并且题目中明确了 n >= 1。
所以建议只初始化 dp[1] = 1, dp[2] = 2，然后从 i = 3 开始递推。
- 确定遍历顺序
从递推公式 dp[i] = dp[i – 1] + dp[i – 2] 中可以看出，遍历顺序一定是从前向后遍历的
- 举例推导 dp 数组
举例当 n 为 5 的时候，dp 数组应该是 [1, 2, 3, 5, 8]
如果代码出问题了，就把 dp 数组打印出来，看看究竟是不是和自己推导的一样。
另外，本题若使用递归会超时
三、代码
public class T70 {
// 非压缩版本
public int climbStairs2(int n) {
// 当 n=1 或者 n=2时，直接返回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];
}
// 压缩版本
public int climbStairs(int n) {
if (n <= 2)
return n;
int first = 1, second = 2, third = 0;
for (int i = 3; i <= n; i++) {
third = first + second;
first = second;
second = third;
}
return third;
}
}