【算法】一文带你快速入门动态规划算法以及动规中的空间优化

这篇具有很好参考价值的文章主要介绍了【算法】一文带你快速入门动态规划算法以及动规中的空间优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++

君兮_的个人主页

即使走的再远,也勿忘启程时的初心

C/C++ 游戏开发

Hello,米娜桑们,这里是君兮_,如果给算法的难度和复杂度排一个排名,那么动态规划算法一定名列前茅。在最开始没有什么整体的方法的时候,我也曾经被动态规划折磨过很长时间,通过我一段时间的刷题和不断的学习,逐渐有了一套自己有关动态规划算法的心得和经验,今天就通过一些比较简单的题目带大家快速上手动态规划算法

  • 好了废话不多说,开始我们今天的学习吧!!

一 什么是动态规划算法

  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
  • 动态规划算法的基本思想是:将原问题分解为若干个子问题,逐个求解子问题,记录每个子问题的解,避免重复计算,最终得到原问题的解。动态规划算法通常用于具有重叠子问题和最优子结构性质的问题,
  • 好了,相信上面这段话没有基础你应该是看不懂的,我们直接说人话
  • 动态规划算法适用于把一个复杂的问题分解成多个子问题,通过解决子问题的方式得到有关原问题的有效信息,最终通过不断的递推得到原问题的解
  • 核心思想就是分治或者说递推,从题目中给的有效信息中最终推出我们想要的结果

动态规划算法的大致公式

不必严格照着这个公式走,前面的步骤是一样,后面的步骤具体问题具体分析即可

  • 1.状态表示
    分析题目,根据题目的要求找出相同的子问题。找出dp表(一般是一维数组或者二维数组)里面的值的含义是什么?(一般都是我们要求的量)

  • 2.状态转移方程
    分析子问题之间的联系(及dp表里各位置中的值的联系),推出一个类似于递推公式的状态转移方程。

  • [x]3.初始化
    为了保证我们在填dp表时不出现越界访问这种情况,我们需要对边界值进行判断以及通过有效信息来对dp表中的边界值进行初始化

  • 4.填表顺序
    在进行上述的几步操作后,我们需要把我们的dp表填满来解决实际问题了,此时是从大到小填还是从小到大填,我们要根据上述操作得到的有效信息结合题目实际具体判断

  • 5.返回值
    把dp表填满后,我们要结合题目要求确定返回值来解题了

  • 我知道,在这里干讲方法没人能听的懂,下面就通过上述这个解题方法带大家来解决几个实际问题。


1 求第 N 个泰波那契数

  • 原题leetcode链接在这里 第 N 个泰波那契数
    【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++
  • 这个可谓是最经典又最简单的动态规划算法题目了,正合适带大家入门,下面我来带大家分析一下题目

算法原理解析

  • 1 状态表示
    给一个整数n 要求我们返回第n个泰波那契数,那么毫无疑问,我们的dp表中的每一个位置表示的就是当n等于这个数时此时的泰波那契数了,也就是 dp[ i ] 表示第i个泰波那契数。
  • 2.状态转移方程
    找出各个dp[i]的值之间的联系,这个题目已经告诉我们了,第i个泰波那契数就是前三个泰波那契数之和,因此我们可以列出下面这个状态转移方程
       dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
  • 3.初始化
    确定dp表的状态转移方程后,我们为了防止越界需要对边界加以判断
    数组的下标是从0开始的 因此当我们对i<3的dp[ i ]进行递推时,就会出现下标越界的情况,因此我们需要对dp[0].dp[1].dp[2]进行初始化,而题目条件也告诉我们了前三个泰波那契数的值(往往我们也可以通过题目给的值来倒推哪些地方需要注意越界提前初始化)
  • 4.填表顺序
    我们知道前三个泰波那契数,而我们需要求第n个泰波那契数,毫无疑问dp表应该从小到大填
  • 5 返回值
    题目要求我们返回第N个泰波那契数,也就是dp[N],这样我们就确定了返回值

有了这上面五步的分析,我们就可以开始进行代码的编写了


编写代码

  • 参考代码如下
class Solution {
public:
    int tribonacci(int n) {
       //对可能出现的越界问题进行判断
        if(n==0)return 0;
        if(n==1||n==2)return 1;
        //建立dp表
        vector<int>dp(n+1);
        //初始化
        dp[0]=0;
        dp[1]=dp[2]=1;
        for(int i=3;i<=n;i++)
        {
        	//通过状态转移方程,由已知的dp值推出未知的
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

        }
        //返回第n个泰波那契数
        return dp[n];
    }
};

【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++
ps:不要在意这里的执行用时和消耗内存,实际上这些于leetcode的服务器和你电脑的配置都有一定关系,你的执行用时高不代表你的算法比别人的差哦!

  • 时间复杂度和空间复杂度分析:
    开辟了大小为n+1的vector,循环遍历了dp表一次,时间和空间复杂度均为O(N)。

一个题说明不了什么,我们再来一个稍微有点难度的题帮助大家进一步理解动态规划算法


2 解码方法

原题leetcode链接在这哦 解码方法
【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++
【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++

算法原理解析

一上来很多人可能就蒙了,这怎么拆分成子问题和建立dp表呢?我们一步一步来

  • 1.状态表示
    通过题目的条件,我们选择用以 i 为结尾来分析(以某个位置结尾或者开始是动态规划中非常重要的经验,一定要记住)。其中dp[i]就表示以i为结尾时,此时解码方法的总数
    注意:既然选择了以i为结尾进行状态表示,就不要考虑i+1位置等的值了(以i为开始同理,不要再考虑i-1等位置的值了)
  • 2.状态转移方程
    我们以i为结尾,就可以分为以下两种情况,我通过图片来表示一下
    【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++
    细节由于主要是讲解算法就不多说了,大家自己去考虑一下,其中 a为s[i]的值,b为s[i-1]的值
    根据上述图片,我们是不是就可以得到这样一种状态转移方程
  • dp[ i ]=dp[i-1]+dp[i-2]
  • 3.初始化
    根据状态转移方程,我们可以轻易的看出dp[1]和dp[0]是需要我们手动初始化而不能递归得出的
  • 4.填表顺序
    求一共有几种解码方法自然要从小到大来推和叠加了,因此填表顺序是从小向大
  • 5.返回值
    我们在状态表示时说了,dp[i]表示以i为结尾时,此时解码方法的总数,因此返回值为dp[i]

做好上面这5步后,我们来看看代码怎么编写


编写代码

class Solution {
public:
    
    int numDecodings(string s) {
        //创建dp表
        //状态转换方程
        //初始化
        int n=s.size();
         //处理边界条件 
        if(n==1)
        {
            
            return s[0]!='0';
        }
        vector<int>dp(n);
         dp[0]=s[0]!='0';
       
       if(s[0]!='0'&&s[1]!='0') dp[1]+=1;
       int t=(s[0]-'0')*10+s[1]-'0';
        if(t>=10&&t<=26) dp[1]+=1;

        
        for(int i=2;i<n;i++)
        {
            if(s[i]!='0')
            dp[i]+=dp[i-1];
            t=(s[i-1]-'0')*10+s[i]-'0';
            if(t>=10&&t<=26) dp[i]+=dp[i-2];
        }
        return dp[n-1];

        // //优化边界和初始化
		//多开一个空间 把之前dp[1]的判断直接放入循环中,增加代码复用率
        // vector<int> dp(n+1);
        // dp[0]=1;
        // dp[1]=s[1-1]!='0';
        // for(int i=2;i<=n;i++)
        // {
        //     if(s[i-1]!='0')
        //     dp[i]+=dp[i-1];
        //     int t=(s[i-2]-'0')*10+s[i-1]-'0';
        //     if(t>=10&&t<=26) dp[i]+=dp[i-2];
        // }
        // return dp[n];

    }
};

【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++

  • ps:这里的注释里也是一种完整的方法以及对我们算法的一些繁琐的地方的优化,由于本文主要偏入门动态规划算法,感兴趣大家就自己看看吧,有不懂的地方可以评论区提出或者私信我。

  • 时间复杂度和空间复杂度分析:
    很容易可得出,时间和空间复杂度均为O(N)。


二 空间优化(背包问题)

  • 在动态规划问题中还有一种常用的空间优化思想,这里也一起给大家介绍一下吧

  • 为了方便讲解,这里我们以第 N 个泰波那契数这个题目为例给大家讲解空间优化

  • 在对该题进行解答时,我们开辟了n+1个空间

vector<int>dp(n+1);
  • 我们仔细回顾一下这个题目,会发现,在得到第 N 个泰波那契数时,我们每个数都只用一次就朝前递推了,可是我们还是开辟了n+1大小的空间来保存它,实际上我们只需要四个数 Tn,Tn-1,Tn-2,Tn-3,那么开辟这么大的空间是不是就有点浪费了?
  • 因此,我们在这里使用滚动数组的方法来对空间进行一下优化
class Solution {
public:
    int tribonacci(int n) {
        //含背包机制的空间优化的动态规划算法
        int a=0;
        int b=1,c=1;
        int d=0;
        if(n==0)return 0;
        if(n==1||n==2)return 1;
        for(int i=3;i<=n;i++)
        {
            d=a+b+c;
            a=b;
            b=c;
            c=d;
        }
        return d;
       }
      
};

【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++

  • 四个变量来进行动态规划一样能过,其他类似的问题也可以采用类似的思想来节省空间

总结

  • 好啦,我们今天的内容就先到这里啦!虽然这两个有关动态规划的问题都不算太难,但是把动态规划的基本思想都包含在内了,其次,一下讲那种很难的题大家也不容易理解。弄懂了简单的题目打好基础才更有利于我们之后的学习,因此如果你想弄懂这块的话,这两道题还是建议你认真去做做哦!!
  • 有任何的问题和对文章内容的疑惑欢迎在评论区中提出,当然也可以私信我,我会在第一时间回复的!!

新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!

**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**

【算法】一文带你快速入门动态规划算法以及动规中的空间优化,算法,算法,动态规划,c++文章来源地址https://www.toymoban.com/news/detail-753136.html

到了这里,关于【算法】一文带你快速入门动态规划算法以及动规中的空间优化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【Java】一文带你快速入门Shiro权限框架

    📓推荐网站(不断完善中):个人博客 📌个人主页:个人主页 👉相关专栏:CSDN专栏 🏝立志赚钱,干活想躺,瞎分享的摸鱼工程师一枚 在我们实战开发过程中,对于权限的控制是必不可少的,一个系统中常见的有 普通会员、管理员、超级管理员 等等不同的角色出现。 我们

    2024年02月08日
    浏览(44)
  • 老壁灯带你入门动态规划

    动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。 从字面意义上来理解,就是走一步看一步,边 解决 问题,边对问题进行整体 规划 。 其实,动态规划的本质就是将问题拆分为小的子问题,对小问题的一步步解决,小问题渐渐

    2024年04月14日
    浏览(26)
  • 【前沿技术】一文带你快速入门 K8s

    👉 博主介绍 : 博主从事应用安全和大数据领域,有8年研发经验,5年面试官经验,Java技术专家,WEB架构师,阿里云专家博主,华为云云享专家,51CTO TOP红人 Java知识图谱点击链接: 体系化学习Java(Java面试专题) 💕💕 感兴趣的同学可以收藏关注下 , 不然下次找不到哟

    2024年02月16日
    浏览(44)
  • 一文带你入门Arco Design,快速构建一个Arco项目Demo

    确保你的机器中有Node.js和Git环境,如果没有,参考如下文章: Node.js安装及环境配置 Git安装配置教程 开始开发之前,请确认本地环境中安装好了 node , git 和 arco cli 其中 arco cli 是安装项目模版的工具,请运行以下命令安装: 在某一个文件夹下运行Shell,运行如下命令新建项

    2024年02月13日
    浏览(43)
  • 扔掉抽象难懂专业名词,带你从头开始理解入门动态规划1

    注:并非指专业名词概念不好,而是认为乍一接触dp就开始啃那些难得名词比较容易劝退,这里用简单的思维理解来了解入门dp。 1.动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 2.由于动态规划并不是某种具体的算法,而是一种解决特定问

    2024年02月03日
    浏览(43)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(95)
  • [算法]动态规划以及常见例题

    之前买的假书害人捏......不过有个问题没说错,动态规划和递归很相似,但是动态规划利用分治法 ,把大问题转化为子任务,当计算出 一个子任务的结果将储存 起来, 避免对于同一个子任务的重复计算 但其实根据某本书的写法,就是给递归套了一层存储的壳子......这个做法其实其

    2024年02月04日
    浏览(47)
  • 动态规划详解(完结篇)——如何抽象出动态规划算法?以及解题思路

    今天直接开始讲解 FIRST:如何抽象出动态规划算法? 这个问题,困扰了无数代OIER,包括本蒟蒻 在比赛的时候,看一道题,怎么想到他是什么算法的呢? 这就需要抽象能力 而不同的算法,往往有着不同的特点 就来说说动态规划的题目特点 通过遍历,能够把所有的情况考虑到

    2023年04月08日
    浏览(39)
  • 【算法入门】浅谈动态规划

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

    2024年04月12日
    浏览(41)
  • 动态规划入门:斐波那契数列模型以及多状态(C++)

        动态规划(Dynamic programming,简称 DP)是一种解决多阶段决策问题的算法思想。它将问题分解为多个阶段,并通过保存中间结果来避免重复计算,从而提高效率。 动态规划的解题步骤一般分为以下几步: 思考状态表示,创建dp表(重点) 分析出状态转移方程(重点) 初始化 确定

    2024年02月11日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包