class Solution {
public int climbStairs(int n) {
//台阶1和2的方法直接返回即可
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
//定义最终台阶以及最终台阶前俩个台阶的方法数
int pre1 = 1;
int pre2 = 2;
int step = 0;
//从第三个台阶开始,f(n)=f(n-1)+f(n-2)
for(int i = 3;i <= n;i++){
step = pre1 + pre2;
pre1 = pre2;
pre2 = step;
}
return step;
}
}
这题使用到了斐波那契数列：f(n)=f(n-1)+f(n-2)
我们想一下，最后一步到楼顶有两种方法，一种是在n-1一步跨上去，再一种就是n-2两步跨上去，所以最后一步一共有到（n-1）阶的方法数加上（n-2）阶的方法数。
判断一道题能不能使用动态规划主要看一下有没有这两个特点：
1.最优子结构，也就是能不能将大问题拆解为小问题
2.重叠子问题，也就是小问题是不是被反复计算
解决问题的三步：
1.定义状态（你想记录的是什么）：比如此题中我们记录的是最终的方法总数step，也就是f(n)
2.找出状态转换的方程：也就是前后怎样联系的，就是找规律，此题爬楼梯的规律是：f(n)=f(n-1)+f(n-2)，也就是斐波那契数列
3.确定初始边界：也就是最基础不能再拆解的基础条件，此题中就是f(1)=1,f(2)=2(pre1=1,pre2=2)
关注我带你每天刷题！！！
