动态规划01 三步问题[C++]

这篇具有很好参考价值的文章主要介绍了动态规划01 三步问题[C++]。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  ​​​​​​动态规划01 三步问题[C++],# 动态规划,动态规划,算法,c++,笔记

图源:文心一言

上机题目练习整理,本篇作为动态规划的代码,因为做题入门很少找到带图的讲解(难道是因为太简单,所以没有人嘛),所以干脆自己写一份,供小伙伴们参考~🥝🥝

  • 第1版:在力扣新手村刷题的记录~🧩🧩

编辑:梅头脑🌸

审核:文心一言

题目:面试题 08.01. 三步问题 - 力扣(LeetCode)


🧵面试题 08.01. 三步问题

🧩题目

三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。

示例1:

 输入:n = 3 
 输出:4
 说明: 有四种走法

示例2:

 输入:n = 5
 输出:13

提示:

  1. n范围在[1, 1000000]之间

🌰解题1:数组存放

📇算法思路

  • 算法思想:
    •  由于每一步我们可以选择走1步、2步或3步,并且只能向右走,因此我们可以将问题分解为更小的子问题:到达位置 i 的方式数可以通过到达位置 i-1i-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博客

同博主的博文:🌸随笔03 笔记整理-CSDN博客文章来源地址https://www.toymoban.com/news/detail-840170.html

到了这里,关于动态规划01 三步问题[C++]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(56)
  • 【Java实现】动态规划算法解决01背包问题

    1、问题描述: 一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大? 2、动态规划算法的概述 1)动态规划(Dynamic Progra

    2023年04月09日
    浏览(57)
  • 算法分析与设计——动态规划求解01背包问题

    假设有四个物品,如下图,背包总容量为8,求背包装入哪些物品时累计的价值最多。 我们使用动态规划来解决这个问题,首先使用一个表格来模拟整个算法的过程。 表格中的信息表示 指定情况下能产生的最大价值 。例如, (4, 8)表示在背包容量为8的情况下,前四个物品的最

    2024年02月04日
    浏览(70)
  • C++算法初级11——01背包问题(动态规划2)

    辰辰采药 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时

    2024年02月02日
    浏览(50)
  • 动态规划01背包问题-代码随想录-刷题笔记

    有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品只能用一次 ,求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包 确定dp数组以及下标的含义 是使用二维数组,即 dp[i][j] 表示从下标为[0-i]的物品里任意取,

    2024年02月07日
    浏览(58)
  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(50)
  • LeetCode三步问题(动态规划)

    链接: 三步问题 编写代码 代码优化

    2024年02月15日
    浏览(41)
  • 【学会动态规划】三步问题(2)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 根据题目,我们可以模拟一下走楼梯的过

    2024年02月16日
    浏览(28)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(58)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包