LeetCode 70 爬楼梯
🟢简单
https://leetcode.cn/problems/climbing-stairs/
容易想到如下代码：
class Solution {
public:
int climbStairs(int n) {
if(n==0) return 1;
if(n==1) return 1;
return climbStairs(n-1)+climbStairs(n-2);
}
};
备忘递归
class Solution {
public:
vector<int> dp;
int re(int n) {
if(n==0) return 1;
if(n==1) return 1;
if(dp[n]!=-1) return dp[n];
dp[n] = re(n-1)+re(n-2);
return dp[n];
}
int climbStairs(int n) {
dp = vector<int>(n+1,-1);
return re(n);
}
};
改成动态规划
class Solution {
public:
int climbStairs(int n) {
if(n<=1) return 1;
int pre_pre = 1;
int pre = 1;
for(int i = 2;i<=n;i++){
int tmp = pre;
pre = pre+pre_pre;
pre_pre = tmp;
}
return pre;
}
};