动态规划:从入门到入土系列(一)

这篇具有很好参考价值的文章主要介绍了动态规划:从入门到入土系列(一)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一

前言

本篇是动态规划系列的入门基础题,以"第 n 个泰波那契数"和 "三步问题"为例子.

一、第 n 个泰波那契数

题目来源于:力扣
题目链接:传送门

题目描述:

泰波那契序列 Tn 定义如下:
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例2:

输入:n = 25
输出:1389537

算法讲解:

  1. 创建dp表.
    确定状态表示:用dp[n]表示第 n 个泰波那契数 Tn 的值.
    我们要返回Tn的值,也就是第n个泰波那契数,由于T0的存在(即有第0个泰波那契数),所以我们创建dp表的时候,需要创建n+1个大小的数组,即dp[n+1].
    ·需要设置的文字

  2. 初始化.
    前面三个泰波那契数的值题目都已经给出,dp[0]=0,dp[1]=1,dp[2]=1;

  3. 填写dp表.
    根据题目介绍,我们不难得出状态转移方程是:Tn+3 = Tn + Tn+1 + Tn+2
    即:Tn = Tn-3 + Tn-2 + Tn-1

动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++

本题中是直接给出了状态转移方程,大多数动态规划的题目是需要我们自己推导的.

  1. 确认返回值.
    题目要求返回第 n 个泰波那契数 Tn 的值,那dp[n]不就是我们需要返回的吗?
  2. 细节处理:
    由于0<n<=2时,无法进行完整的初始化操作,我们可以提前进行判定直接返回.

代码实现:

class Solution {
public:
    int tribonacci(int n) {
        //防止因为n过小导致的初始化问题
        if(n==0) return 0;
        if(n==1||n==2)return 1;

        //1.创建dp表
        int dp[n+1];
        //2.初始化
        dp[0]=0,dp[1]=1,dp[2]=1;
        //3.填表
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        }
        //4.确认返回值
        return dp[n];
    }
};

空间优化:

在上面的算法中,我们创建了n+1个大小的数组空间,所以空间复杂度是O(n),我们可以采用滚动数组的方法,将时间复杂度降到O(1).

其实我们可以不用创建n+1个大小的数组空间,因为只需要知道第n项的前三个,就可以推导出第四项,所以我们可以创建只有四个大小的数组空间.

动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++

class Solution {
public:
    int tribonacci(int n) {
        //防止因为n过小导致的初始化问题
        if(n==0) return 0;
        if(n==1||n==2)return 1;

        //1.创建dp表
        int dp[4];
        //2.初始化
        dp[0]=0,dp[1]=1,dp[2]=1;
        //3.填表
        for(int i=3;i<=n;i++)
        {
            dp[3]=dp[2]+dp[1]+dp[0];
            //动态更新数组(滚动数组)
            dp[0]=dp[1];
            dp[1]=dp[2];
            dp[2]=dp[3];
        }
        //4.确认返回值
        return dp[3];
    }
};

动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++

二、三步问题

题目来源于:力扣
题目链接:传送门

题目描述:

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

示例1:

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

示例2:

输入:n = 5
输出:13

算法讲解:

  1. 创建dp表:
    确定状态表示:dp[n]代表有n阶楼梯时,小孩可以选择上楼的方式.
    我们要j计算的是当有n阶台阶时,小孩有多少种上楼梯的方式.
    并且此题规定:0个台阶时,有一种上楼方式.
    所以我们创建dp表的时候,需要创建n+1个大小的数组,即dp[n+1].

  2. 初始化:
    上楼梯的方法:dp[0]=1,dp[1]=1,dp[2]=2;

  3. 填写dp表.
    先看懂题目意思,此题需要自行推导状态转移方程.
    分析: dp[0]=1,dp[1]=1.

动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++
4. 确认返回值:
dp[n]代表有n阶楼梯时,我们可以选择的上楼方式.所以返回dp[n]即可.

5.细节处理:
(1)由于0<n<=2时,无法进行完整的初始化操作,我们可以提前进行判定直接返回.
(2)由于这里数据比较大,所以每次进行"+"运算时,需要进行对结果取模(1000000007).

代码实现:

class Solution {
public:
    int waysToStep(int n) {
        const int MOD =1000000007;
        
        //防止因为n过小导致的初始化问题
        if(n==0||n==1)return 1;
        if(n==2)return 2;
		
		//创建dp数组
        int dp[n+1];
        //初始化操作
        dp[0]=1,dp[1]=1,dp[2]=2;
        //填表
        for(int i=3;i<=n;i++)
        {
            dp[i]=((dp[i-3]+dp[i-2])%MOD+dp[i-1])%MOD;//这里一定要记得取模
        }
        //返回值
        return dp[n];
    }
};

运行结果:
动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++

当然也可以使用滚动数组的方式进行空间优化,这里就不再演示了.

三、 结语:

本篇是动态规划系列的入门基础题,题目难度偏简单,后续会慢慢更新,难度有所提升.
下篇见!
动态规划:从入门到入土系列(一),动态规划,动态规划,算法,c语言,c++文章来源地址https://www.toymoban.com/news/detail-589745.html

到了这里,关于动态规划:从入门到入土系列(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 60题学会动态规划系列:动态规划算法第二讲

    都是路径问题~ 文章目录 1.不同路径 2.不同路径II 3.礼物的最大价值 4.下降路径最小和 5.最小路径和 力扣链接:力扣 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在

    2024年02月07日
    浏览(59)
  • “算法详解”系列第3卷贪心算法和动态规划出版

    “算法详解”系列图书共有4卷,目前1到3卷已经出版。最新出版的是第3卷—贪心算法和动态规划。 “算法详解”系列图书共有4卷,本书是第3卷—贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、集群、哈夫曼编码等,动态规划主要包括背包、序列对齐、最短

    2024年02月13日
    浏览(37)
  • 运筹系列87:julia求解随机动态规划问题入门

    随机动态规划问题的特点是: 有多个阶段,每个阶段的随机性互不相关,且有有限个实现值 (finite realizations) 具有马尔可夫性质,即每个阶段只受上一个阶段影响,可以用状态转移方程来描述阶段与阶段之间的变化过程。 我们使用julia的SDDP算法包来求解随机动态规划问题。

    2024年01月16日
    浏览(43)
  • 【算法入门】浅谈动态规划

    关于动态规划的定义,网上有很多,但对于初学者,看了定义之后,多少会有点懵,接下来我打算用俩到三个例题来引入动态规划的定义,我将动态规划分为动态和规划俩部分,动态说明它是变化的,规划说明它是从前到后的,所以综合下来就是后面的由前面或者说受前面影

    2024年04月12日
    浏览(41)
  • 算法沉淀——动态规划篇(子数组系列问题(下))

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具体依题目而

    2024年04月14日
    浏览(52)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

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

    2024年04月16日
    浏览(56)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(45)
  • 动态规划系列 | 状态机模型(上)| 练完这些就算入门了!

    用状态机模型求解动态规划问题,就是将原始问题用状态机模型进行表示,即 每个节点表示状态,每条边表示一个状态转移,边上的权值表示转移的代价或收益 。 状态机模型的目标是 找到一条从初始状态出发,经过若干次状态转移,达到某个终止状态的路径,使得最终的结

    2024年02月22日
    浏览(42)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(43)
  • 算法套路十三——动态规划DP入门

    动态规划和递归都是通过将大问题分解为较小的子问题来解决问题。它们都可以用来解决具有重叠子问题和最优子结构特性的问题。 递归是一种自顶向下的方法, 它从原始问题开始 ,递归地将问题分解为较小的子问题dfs(i)—— dfs(i)代表的是从第i个状态开始进行递归求解能

    2024年02月15日
    浏览(60)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包