70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
- 输入： 2
- 输出： 2
- 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
- 输入： 3
- 输出： 3
- 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解题思路：
刚开始做的时候没有反应过来，不过做这种题的时候还是旁边有个纸和笔比较好，在纸上写写，发现找出来规律了，卧槽，这不就是斐波那契数列吗？！！！
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
我们来分析一下，动规五部曲：
定义一个一维数组来记录不同楼层的状态
- 确定dp数组以及下标的含义
dp[i]： 爬到第i层楼梯，有dp[i]种方法
- 确定递推公式
如何可以推出dp[i]呢？
观察题目的要求，每次可以爬 1 或 2 个台阶，那么对于第 n 阶楼梯来说，要到达第 n 阶只有两种可能性：
- 从第 n-1 阶爬一步到达第 n 阶；
- 从第 n-2 阶爬两步到达第 n 阶。
因此，到达第 n 阶楼梯的方法数等于到达第 n-1 阶楼梯的方法数加上到达第 n-2 阶楼梯的方法数，即：
dp[n] = dp[n-1] + dp[n-2]
这正是斐波那契数列的递推关系式。所以，这个问题可以通过计算斐波那契数列的第 n 项来得到答案。
要注意的是，对于这个问题，初始情况下第 0 阶和第 1 阶的方法数都是 1，即：
dp[0] = 1
dp[1] = 1
然后，通过递推关系式计算 dp[2]、dp[3]、...、dp[n]，最终得到到达第 n 阶楼梯的方法数。
- dp数组如何初始化
再回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]种方法。
那么i为0，dp[i]应该是多少呢，这个可以有很多解释，但基本都是直接奔着答案去解释的。
例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp[0] = 1，相当于直接站在楼顶。
但总有点牵强的成分。
那还这么理解呢：我就认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp[0]就应该是0.
其实这么争论下去没有意义，大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp[0] = 1。
从dp数组定义的角度上来说，dp[0] = 0 也能说得通。
需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。
所以本题其实就不应该讨论dp[0]的初始化！
我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。
所以我的原则是：不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
- 确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
- 举例推导dp数组
当n为5时，推导dp数组的过程如下：
初始情况下，dp[0] = 1，dp[1] = 1，表示到达第0阶和第1阶楼梯的方法数都是1。
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
然后，根据递推关系式dp[i] = dp[i-1] + dp[i-2]，计算dp[2]、dp[3]、dp[4]、dp[5]的值。
- 计算dp[2] = dp[1] + dp[0] = 1 + 1 = 2
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
- 计算dp[3] = dp[2] + dp[1] = 2 + 1 = 3
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
- 计算dp[4] = dp[3] + dp[2] = 3 + 2 = 5
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
- 计算dp[5] = dp[4] + dp[3] = 5 + 3 = 8
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
最终得到dp数组如上所示，dp[5]的值为8，表示到达第5阶楼梯的方法数为8。
代码实现：
/**
* 70.爬楼梯
*/
public class ClimbingStairs {
public int climbStairs(int n) {
if(n == 0 || n == 1){
return n;
}
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i =2;i <= n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}
评论区