图源:文心一言
上机题目练习整理,本篇作为动态规划的代码,因为做题入门很少找到带图的讲解(难道是因为太简单,所以没有人嘛),所以干脆自己写一份,供小伙伴们参考~🥝🥝
- 第1版:在力扣新手村刷题的记录~🧩🧩
编辑:梅头脑🌸
审核:文心一言
题目:面试题 08.01. 三步问题 - 力扣(LeetCode)
🧵面试题 08.01. 三步问题
🧩题目
三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
示例1:
输入:n = 3 输出:4 说明: 有四种走法示例2:
输入:n = 5 输出:13提示:
- n范围在[1, 1000000]之间
🌰解题1:数组存放
📇算法思路
- 算法思想:
- 由于每一步我们可以选择走1步、2步或3步,并且只能向右走,因此我们可以将问题分解为更小的子问题:到达位置
i
的方式数可以通过到达位置i-1
、i-2
和i-3
的方式数来推导。这样,我们就可以使用动态规划来逐步构建到达每个位置的方式数,直到到达目标位置n;
- 算法的关键在于正确地定义状态(在这里是
dp[i]
)和状态转移方程(在这里是dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
,但需要注意边界条件,确保不会访问数组的负索引)。- 时间复杂度:O(n),n是需要到达的目标位置,使用了1个循环,遍历步数i(从1到n);
- 空间复杂度:O(n),代码使用了一个一维数组dp来存储到达每个位置的方式数;
⌨️算法代码
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007; // 取模的大质数
class Solution {
public:
int waysToStep(int n) {
vector<int> dp(n + 1, 0); // 一维数组,dp[i] 表示到达位置 i 的方式数
dp[0] = 1; // 初始条件,到达位置 0 的方式数为 1
for (int i = 1; i <= n; i++) {
// 遍历到达位置 i 的所有可能的前一步位置
for (int j = 1; j <= 3 && i - j >= 0; j++) {
dp[i] += dp[i - j] % MOD; ; // 累加从各个前一步位置到达位置 i 的方式数,并取模
}
// 输出测试
// cout << "dp after step " << i << ": ";
// for (int k = 0; k <= i; k++) {
// cout << dp[k] << " ";
// }
// cout << endl;
}
return dp[n]; // 返回到达位置 n 的方式数
}
};
/*
int main() {
Solution solution;
int a = solution.waysToStep(3);
cout << "Number of ways to step to position 3: " << a << endl;
return 0;
}
*/
作者:文心一言
📇代码解释
1:状态方程
- 小孩走向第 i 级台阶的位置可以是:
- 从第 i−1 阶迈 1 阶;
- 从第 i−2 阶迈 2 阶;
- 从第 i−3 阶迈 3 阶;
- 那么状态方程可以是:
- dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];代码等价的表示为:for (int j = 1; j <= 3 && i - j >= 0; j++) { dp[i] += dp[i - j] };
- 根据题目要求,为了避免整数溢出问题,确保结果在计算机的整数表示范围内,执行取余操作,而
1000000007
这是一个常见的大质数,因此算式:dp[i] = (dp[i] + dp[i - j]) % MOD;- 初始状态:第0个台阶有1种方式(不动);
- i 的范围:从1走向n级台阶;
2:算法模拟
注意,动态数组就是一种记忆的工具,它可以记录到达 i-1 、i-1、i-3的跳法,因此计算 i 时仅用 i 的前3轮的跳法相加即可;
举个栗子,例如跳到台阶3,它有4种方法到达:
- 1次跳3级,从0级台阶跳到3级台阶;而跳到dp[0]仅1种跳法,在第2轮的dp[0]中记录,因此dp[0]→dp[3]也是唯一跳法;
- 1次跳2级,从1级台阶跳到3级台阶;而dp[0]跳到dp[1]仅1种跳法,在第2轮的dp[1]中记录,因此dp[1]→dp[3]也是唯一跳法;
- 1次跳1级,从2级台阶跳到3级台阶;而dp[0]跳到dp[2]有2种跳法,在第2轮的dp[2]中记录,因此dp[2]→dp[3]也是2种跳法;
- 相加,dp[0] + dp[1] + dp[2] = 4,即为4种台阶跳法~~
轮数 / 跳法 | dp[0] | dp[1] | dp[2] | dp[3] | 备注 |
---|---|---|---|---|---|
初始 | 1 | ||||
第1轮 | 1 | 1 | 1:dp[0]→dp[1] | ||
第2轮 | 1 | 1 | 2 | 1:dp[0]→dp[1]→dp[2] 2:dp[0]→dp[2] |
|
第3轮 | 1 | 1 | 2 | 4 | 1:dp[0]→dp[1]→dp[3] 2:dp[0]→dp[1]→dp[2]→dp[3] 3:dp[0]→dp[2]→dp[3] 4:dp[0]→dp[3] |
🌰解题2:变量存放
⌨️算法代码
class Solution {
public:
int waysToStep(int n) {
if(n<3) return n; // 跳到台阶1有1种方法,跳到台阶2有2种方法
int base=1e9+7; // 取模质数
int dp0=1,dp1=2,dp2=4; // 初始化3种状态:跳到台阶dp0有1种方式,跳到台阶dp1有2种方式,跳到台阶dp2有3种方式
int temp1,temp2; // 记录 dp[i-1],dp[i-2]
while(n--!=3){ // 台阶数n不等于3时,执行循环,并且n-1
temp1=dp1,temp2=dp2; // 使用temp1和temp2保存dp1和dp2的值,因为dp1和dp2即将被更新
dp2=((dp0+dp1)%base+dp2)%base; // 走到第n个台阶的方法数等于走到第n-1, n-2, n-3个台阶的方法数之和
dp0=temp1,dp1=temp2; // 更新dp0和dp1为上一轮的dp1和dp2
}
return dp2; // 循环结束后,dp2中存储的就是走到第n个台阶的方法数
}
};
作者:treasure_
链接:https://leetcode.cn/problems/three-steps-problem-lcci/solutions/529898/c-dong-tai-gui-hua-by-treasure_-611d/
- 时间复杂度:O(n),n是需要到达的目标位置,使用了1个循环,遍历步数i(从1到n);
- 空间复杂度:O(1),不同于方法一使用数组,方法二使用了3个常数存放状态,只要更新temp1、temp2、dp2、dp0,就可以实现状态方程dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]的功能;
- 备注:
- 算法代码1、2在思路上非常相似,只是语法的细节有些不同;
- 算法2我已经逐行注释在了旁边,算法思路不再赘述【emm...如果真的需要再详细解说1遍,欢迎小伙伴在评论区留言】。
🔚结语
博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等,博主会顶锅前来修改~~😶🌫️😶🌫️
我是梅头脑,本片博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下,感谢点赞小伙伴对于博主的支持~~🌟🌟
同系列的博文:🌸动态规划_梅头脑_的博客-CSDN博客文章来源:https://www.toymoban.com/news/detail-840170.html
同博主的博文:🌸随笔03 笔记整理-CSDN博客文章来源地址https://www.toymoban.com/news/detail-840170.html
到了这里,关于动态规划01 三步问题[C++]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!