1.题目
假设你正在爬楼梯。需要?n?阶你才能到达楼顶。
每次你可以爬?1?或?2?个台阶。你有多少种不同的方法可以爬到楼顶呢？
来源：70. 爬楼梯 - 力扣（LeetCode）
2.解题思路
? ? ? ? 这道题不应该去考虑排列组合，比较麻烦。
? ? ? ? 一种比较巧妙地做法是用动态方程，求到达n阶的种类时，可以转换为求低阶级的种类。
? ? ? ? Why?
? ? ? ? 走楼梯可以走1步，也可以走2步.
? ? ? ? 所以到达n阶时，要么是从n-1阶一步上来，要么从n-2阶一次性走2步，
? ? ? ? 则到达n阶的次数f(n)=f(n-1)+f(n-2)
? ? ? ? 考虑初始情况，n=0时，f(0)=1,n=1时，f(1)=1。
????????然后开始写代码.
? ? ? ? 上边那个动态方程很明显可以用递归的形式去写：
int climbStairs(int n) {
if(n==1 or n==0){
return 1;
}
return climbStairs(n-1)+climbStairs(n-2);
}
???????????但是，很不幸的是递归算法运行超时。
? ? ? ? 可以考虑用变量去保存计算出的到达第i-1层和第i-2层的种类，这样就不用才通过递归做重复的计算了。分别设置变量a1,a2,a3分别表示前两层的种类数，a3表示目前的种类数。
? ? ? ? 代码执行过程相当于数组不断向前滚动，最后的a3就是最后的结果。
3.代码
class Solution {
public:
int climbStairs(int n) {
int a1=0,a2=0,a3=1;
for(int i=1;i<=n;i++){
a1=a2;
a2=a3;
a3=a1+a2;
}
return a3;
}
};
|