70. 爬楼梯

目录

一.题目描述

二.解题思路

三.代码

四.重点

一.题目描述

假设你正在爬楼梯。需要 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

二.解题思路

①核心规律（解题关键）：达到第3个台阶的方法数 = 达到第1个台阶的方法数（因为是第1个台阶迈两步上来的） +  达到第2个台阶的方法数（因为是第2个台阶迈一步上来的）。

抽象为表达式：dp[ i ] = dp[ i-2 ] + dp[ i-1 ]

我们此时没抽象成数组，而是抽象成了一个变量（都一样，能状态转换，让for循环跑起来就行）：

int current = prev2 + prev1;//计算达到当前台阶的总数：往前数两个的那个台阶的方法数 + 往前数一个的那个台阶的方法数

②由于这道题规定了每次最多爬2个台阶，因此我们要有一个分工意识。即：

• 当n<=2时，用if判断，单独返回步数，因为简单很好判断（起步）
• 当n>2时，需要用for循环来实现动态规划算法（状态压缩+状态转换），来计算达到第n个台阶的最大方法数（跑起来，不断进行状态转换，最终求出结果）

③由于这道题规定了每次最多爬2个台阶，因此我们只需要定义2个初始变量（prev2、prev1）。同理，如果以后这道题换一个出法，比如每次最多可以爬3个台阶，那么就需要定义3个初始变量（prev3、prev2、prev1）了，这也很好理解，因为后续需要进行状态转换。

④关键思想：用for循环实现动态规划算法的时候，其实就是模拟从下慢慢往上爬的过程，每爬一步以后，prev2、prev1就需要更新最新的值。比如：我现在在第三个台阶，此时的前两个台阶是第一阶，前一个台阶是第二阶。那么当我往上爬了一层以后（现在到了第四层），新的前两个台阶就变成了第二阶，新的前一个台阶就变成了第三阶。这也不难理解，纯属生活常识。

上述状态转换的过程，就可以写成如下的代码：

• prev2 = prev1;//很好理解，当又往上爬了一个台阶，新的往前数两个的台阶（的最大方法数） = 旧的往前数一个的台阶（的最大方法数）
• prev1 = current;//很好理解，当又往上爬了一个台阶，新的往前数1个的台阶（的最大方法数） = 旧的当前台阶（的最大方法数）

三.代码

class Solution {
public int climbStairs(int n) {
//这个不难理解
//当n=1,方法就1种，1=n
//当n=2,方法就2种，2=n
if(n<=2){
return n;
}

int prev2 = 1;//当前台阶往前数两个的方法数（初始化为第三阶往前数两个：即第1阶，方法数就1个）
int prev1 = 2;//当前台阶往前数一个的方法数（初始化为第三阶往前数一个：即第2阶，方法数有2个）

for(int i=3; i<=n; i++){
//计算达到当前台阶的总数：往前数两个的那个台阶的方法数 + 往前数一个的那个台阶的方法数
//举例：达到第三个台阶的方法数 = 达到第二个台阶的方法数（2） + 达到第一个台阶的方法数（1）= 3
int current = prev2 + prev1;

//状态转换（核心步骤）
prev2 = prev1;//很好理解，当又往上爬了一个台阶，新的往前数两个的台阶 = 旧的往前数一个的台阶
prev1 = current;//很好理解，当又往上爬了一个台阶，新的往前数1个的台阶 = 旧的当前台阶
}

//最后的prev1就是所求的值（思考为什么不是current？因为for循环结束时，把current赋给了prev1）
return prev1;

}
}

运行效果

四.重点

①知道初始变量怎么定义（本题是根据一次最多迈多少个台阶来决定的）

②知道解题的分工：用if解决前2个台阶，用for解决2~n个台阶

③知道状态转换的逻辑：

• prev2 = prev1;//很好理解，当又往上爬了一个台阶，新的往前数两个的台阶 = 旧的往前数一个的台阶
• prev1 = current;//很好理解，当又往上爬了一个台阶，新的往前数1个的台阶 = 旧的当前台阶

本题只是一个简单的动态规划问题，希望它成为一个引子，启蒙大家对于动态规划算法的学习。