爬楼梯
爬楼梯
2023-09-14 09:02:34 时间
爬楼梯
递归解法
- 递归解法的关键在于要找到函数恒等式,即推导公式f(n)=f(n-1)+f(n-2)
class Solution {
public:
int climbStairs(int n)
{
//注意:这里终止条件有两个
if(n==1)
return 1;
if(n==2)
return 2;
//3.本级递归干什么:计算当前层的爬法总数
int ret=climbStairs(n-1)+climbStairs(n-2);
//2.返回当前层n的爬法总数
return ret;
}
};
- 那么有什么办法可以让递归解法不超时呢?
- 记忆化递归
- 在上一种方法中,我们计算每一步的结果时出现了冗余。另一种思路是,我们可以把每一步的结果存储在 memo
- 数组之中,每当函数再次被调用,我们就直接从 memo 数组返回结果。
- 在 memo数组的帮助下,我们得到了一个修复的递归树,其大小减少到 nn 。
class Solution {
public:
int climbStairs(int n)
{
int* ret = new int[n+1];
return climb(0,ret, n);
}
//这里注意ret数组0号位置存放的是n阶楼梯总爬法的可能
//数组最后一个元素是1阶楼梯爬法总数
int climb(int i,int ret[],int n)
{
if (i> n)
{
return 0;
}
else if (i == n)
{
return 1;
}
else if (ret[i] > 0)
{
return ret[i];
}
else
{
return ret[i] = climb(i + 1, ret, n) + climb(i + 2, ret, n);
}
}
};
动态规划
- 本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于 2 部分之和
1.爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
2.爬上 n−2 阶楼梯的方法数量,因为再爬2阶就能到第n阶 - 所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
- 同时需要初始化 dp[0]=1 和 dp[1]=1
- 时间复杂度:O(n)
class Solution {
public:
int climbStairs(int n)
{
int* dp = new int[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];
}
};
官方提供的更高级版本的动态规划—滚动数组
class Solution {
public:
int climbStairs(int n)
{
int p=0,q=0,r=1;
for(int i=1;i<=n;i++)
{
p=q;
q=r;
r=p+q;
}
return r;
}
};
- 此题还有矩阵快速幂解法和通项公式解法,有兴趣的可以去官方题解看看
相关文章
- 爬楼梯
- Java实现 LeetCode 746 使用最小花费爬楼梯(递推)
- Java实现 LeetCode 746 使用最小花费爬楼梯(递推)
- Java实现 LeetCode 746 使用最小花费爬楼梯(递推)
- Java实现 LeetCode70 爬楼梯
- Java实现 LeetCode70 爬楼梯
- Java实现 LeetCode70 爬楼梯
- LeetCode(70): 爬楼梯
- 算法练习之x的平方根,爬楼梯,删除排序链表中的重复元素, 合并两个有序数组
- 每日一道 LeetCode (17):爬楼梯
- LeetCode(70): 爬楼梯
- LeetCode-70. 爬楼梯【滚动数组,斐波那契数列】
- 70. 爬楼梯
- leetcode 746. 使用最小花费爬楼梯----动态规划篇
- 爬楼梯(C++)
- 746. 使用最小花费爬楼梯-动态规划
- 爬楼梯-c语言力扣最快算法
- Leetcode爬楼梯
- [LeetCode] 746. 使用最小花费爬楼梯 ☆(动态规划)
- leetcode 70. 爬楼梯 js实现
- 70. 爬楼梯
- 【Leetcode刷题Python】70. 爬楼梯
- 【LeetCode】70.爬楼梯
- 【70】爬楼梯【LeetCode】