70 爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/
爬楼梯和斐波那契数不同之处在于:初始值不同
- 爬楼梯n == 1, dp[1] = 1; n == 2, dp[2] = 2
- 斐波那契数n == 0, dp[0] = 0; n == 1, dp[1] = 1; n == 2, dp[2] = 1;
解法一:递归
class Solution {
public:
int climbStairs(int n) {
if(n <= 1)
return 1;
return climbStairs(n - 1) + climbStairs(n - 2);
}
};
时间复杂度:\(O(2^n)\)
可视为二叉树,树高为n,节点数为\(2^n\),遍历搜索树需要\(2^n\)次
空间复杂度:\(O(n)\)
n个栈空间
解法二:记忆化搜索
class Solution {
private:
vector<int> m;
int dfs(int n){
if(n <= 1)
return 1;
int &res = m[n];
if(res)
return res;
return dfs(n - 1) + dfs(n - 2);
}
public:
int climbStairs(int n) {
m.resize(n + 1);
return dfs(n);
}
};
时间复杂度:\(O(n)\)
每个状态只会计算一次,共n个状态
空间复杂度:\(O(n)\)
n个栈空间
解法三:动态规划
class Solution {
public:
vector<int> dp;
int climbStairs(int n) {
dp.resize(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];
}
};
时间复杂度:\(O(n)\)
状态数n * 状态计算1次
空间复杂度:\(O(n)\)
n个状态
解法四:空间优化
class Solution {
public:
int climbStairs(int n) {
int a = 0, b = 1, c;
for(int i = 1; i <= n; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
};
时间复杂度:\(O(n)\)
状态数n * 状态计算1次
空间复杂度:\(O(1)\)
只需3个变量