LeetCode 70. 【滚动数组】爬楼梯
原题链接
简单
作者:
大明湖的鱼
,
2021-01-14 11:07:27
,
所有人可见
,
阅读 229
递归超时代码,里面重复运算太多
class Solution {
public:
int ans = 0;
int climbStairs(int n) {
dfs(0,n);
return ans;
}
void dfs(int i,int n){
if(i > n ) return ;
else if(i == n) ans++;
else {
dfs(i+1,n);
dfs(i+2,n);
}
}
};
斐波那契数列,时间击败100,空间99
- 第n阶台阶只能从第n-1阶或n-2阶 到达,所以【n阶的方案 = n-1阶方案 + n-2阶方案】
- 和斐波那契数列前n项不占额外空间类似
代码
class Solution {
public:
int ans = 0;
int climbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int a = 1, b = 2, temp;
for(int i = 3; i <= n ;i++){
temp = a ;
a = b;
b = temp +b;
}
return b;
}
};