【算法小课堂】动态规划

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

动态规划

动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是叙述概念,讲解原理,让人觉得晦涩难懂,即使一时间看懂了,发现当自己做题的时候又会觉得无所适从。我觉得,理解算法最重要的还是在于练习,只有通过自己练习,才可以更快地提升。话不多说,接下来,下面我就通过一个例子来一步一步讲解动态规划是怎样使用的,只有知道怎样使用,才能更好地理解,而不是一味地对概念和原理进行反复琢磨。

本题很明显

  1. 状态表示dp【i】为第n个泰波那契数,【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式
  2. 编辑本题是第一种情况,后面的题目我们会不断遇到1,2,3的情况,我们后面再细讲
  3. 而状态转移方程为题目也直接给了出来, Tn+3 = Tn + Tn+1 + Tn+2,状态转移方程: Tn = Tn -1+ Tn-2 + Tn-3
  4. 初始化(防止越界的情况):本题很明显Tn-3的时候当,n小于3的时候会出现越界的情况,因此我们要提前初始化好dp【0】 ,dp【1】,dp【2】
  5. 填表顺序: 左到右【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式编辑
  6. 返回值;dp【n】

细节问题:

  • 当n<3的时候,就不需要进行Tn = Tn -1+ Tn-2 + Tn-3计算因此就可以直接返回

空间优化问题:

本题如果我们按照上面的写法的话,就需要开辟一个n+1大小的vector数组dp,当我们在计算第n个位置的时候,我们只需要n-1,n-2,n-3的位置,如果前面还有n-4和n-5都不需要的

【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式

因此我们就可以直接用三个变量a,b,c来优化,使得空间复杂度为o(1)

面试题 08.01. 三步问题

分析一下题目的意思:

当从0号台阶到1号台阶,只有1种方法;

当从0号台阶到2号台阶,我们可以直接从0号台阶蹦到2号台阶,也可以从0-1-2,总共两种解法

当从0号台阶到3号台阶,我们可以从0号直接蹦到3号台阶,也可以0-1-2-3和0-2-3和0-1-3,总共4种解法

【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式编辑 眼尖的同学这个时候以及发现了状态转移方程了,我们注意一下(以到4号台阶为例):我们可以看成从1号到4的方法数+2号到4号的方法数+3号到4号的方法数

  1. 因此我们的状态表示dp【i】就表示到达第i号台阶的方法数
  2. 状态转移方程:【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式编辑

此时有的同学会有一个疑问:就是我从i-2号台阶到i号台阶的时候不是有两种情况:

  • i-2到i
  • i-2先到i-1再到i号台阶

其实不然:i-2先到i-1的这种情况以及是包含在i-1到i的方法数中

  1. 初始化(防止越界的情况):本题很明显Tn-3的时候当,n小于3的时候会出现越界的情况,因此我们要提前初始化好dp【0】 ,dp【1】,dp【2】
  2. 填表顺序: 左到右
  3. 返回值;dp【n】

解题思路:

本题的状态表示是通过经验+题目要求得出的

状态表示:dp[i]代表以i位置结尾的所有解码方法总和

状态转移方程:

【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式编辑

我们就观察以i位置结尾的数字串,此时有两种情况:

  • s[i]单独解码
  • s[i]和s[i-1]一起解码

先说s【i】单独解码的情况,当解码成功时,也就是s【i】代表的数字属于【1,9】,则dp【i】+=dp【i-1】,失败的话就是0了

再来就是 s[i]和s[i-1]一起解码 的情况:当解码成功也就是这两个数字属于【10,26】,则dp【i】+=dp【i-2】,失败也是0

初始化:dp【0】当s【0】属于1-9,dp【0】=1,s【0】=0的话dp【0】=0

dp【1】的话,此时就有两个数字,就分为两种情况,两个数字分开单独解码和两个数字一起解码,单独解码的话s【1】代表的数字属于【1,9】,dp【1】++,两个数字一起解码的话,当解码成功也就是这两个数字属于【10,26】,则dp【1】++

填表顺序:从左导游

返回值;dp[n-1]

解题代码:

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int>dp(n + 1, 0);
        //初始化
        if (s[0] >= '1' && s[0] <= '9')dp[0] = 1;
        else dp[0] = 0;
        if (n == 1)return dp[0];

        if (dp[0] && s[1] - '0')dp[1]++;
        int num = (s[0] - '0') * 10 + (s[1] - '0');
        if (num >= 10 && num <= 26)dp[1]++;

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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

91. 解码方法

处理边界问题及初始化问题的的技巧:

我们可以给dp数组多开一个位置,也就是开n+1个空间,使整个数组向右移动一位

这样我们原本的dp【1】也可以移到循环中进行计算了!!!

【算法小课堂】动态规划,算法小课堂,算法挨揍日记,算法,动态规划,代理模式编辑

这里的0,1,2等都是下标

因此我们多出来一个位置0号下标的值是多少呢?

因为我们后面要计算dp【2】也就是原本的dp【1】的时候会运用到dp【i-2】和dp【i-1】

因为dp【i-1】不会出错,所以我们只需要注意dp【i-2】的正确性

当dp【2】时,也就是两位数字的解码方案数,当我们运用到dp【i-2】的时候,这个是两位数字一起解码,因此dp【i】+=dp【i-2】如果dp【0】为0,即使解码成功也等于没有解码成功,因此这里dp【0】要为1文章来源地址https://www.toymoban.com/news/detail-822189.html

优化后的代码:

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int>dp(n+1);
        dp[0]=1;
        //初始化
        if(s[0]>='1'&&s[0]<='9')dp[1]=1;
        else dp[1]=0;
        if(n==1)return dp[1];

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

到了这里,关于【算法小课堂】动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器

    202. 快乐数 https://leetcode.cn/problems/happy-number/ 编写一个算法来判断一个数  n  是不是快乐数。 「快乐数」  定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是  无限循环  但始终变不到 1。 如果这

    2024年02月11日
    浏览(34)
  • 【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字

       611. 有效三角形的个数 https://leetcode.cn/problems/valid-triangle-number/ 给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边    题

    2024年02月12日
    浏览(46)
  • 【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词

    904. 水果成篮 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组  fruits  表示,其中  fruits[i]  是第  i  棵树上的水果  种类  。 你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果: 你只有  两个

    2024年02月07日
    浏览(37)
  • 动态规划课堂5-----子序列问题(动态规划 + 哈希表)

    目录 引言: 例题1:最长递增子序列 例题2:最长定差子序列 例题3:最长的斐波那契子序列的长度 例题4:最长等差数列 例题5:等差数列划分II-子序列 结语: 要想解决子序列问题那么就要理解子序列和子数组的区别,二者的定义如下。 子序列: 是由数组派生而来的序列,

    2024年03月13日
    浏览(65)
  • 动态规划课堂6-----回文串问题

    目录 引言: 例题1:回文子串 例题2:回文串分割IV 例题3:分割回文串II 例题4:最长回文子序列 例题5:让字符串成为回文串的最小插入次数 回文字符串  是正着读和倒过来读一样的字符串。 动态规划的回文串问题一般是把 子串 是否是回文串的信息保持在dp表里面,所以更

    2024年03月18日
    浏览(46)
  • 动态规划课堂4-----子数组系列

    目录 引入: 例题1:最大子数组和 例题2:环形子数组的最大和 例题3:乘积最大子数组 例题4:乘积为正数的最长子数组 总结: 结语: 在动态规划(DP)子数组系列中,我们还是用前面几节所用的 解题思路1. 状态表示,2.状态转移方程,3.初始化,4.填表顺序,5.返回值 。在

    2024年03月11日
    浏览(35)
  • 动态规划课堂7-----两个数组的dp问题(等价代换)

    目录 引言: 例题1:最长公共子序列 例题2:不同的子序列 例题3:通配符匹配 例题4:正则表达式 结语: 本节我们就要进入 两个数组的dp问题 的学习,通过前面几个章节的学习,相信友友们对动态规划的解题步骤和代码编写步骤已经有了一定的了解(*/ω\*),接下来我会通过

    2024年03月22日
    浏览(38)
  • 设计模式之代理模式(静态代理&动态代理)

    目录 1、什么是代理模式 2、代理模式的结构 3、代理模式的实现 3.1 静态代理和动态代理概念 3.2 静态代理 3.3 动态搭理 3.3.1 代码实现 3.3.2 Proxy类讲解 4、动态代理VS静态代理 5、代理模式优缺点 由于某些原因需要给某对象提供一个代理以控制对该对象的访问。这时,访问对象

    2024年02月03日
    浏览(33)
  • 设计模式8:代理模式-动态代理

    上一篇:设计模式8:代理模式-静态代理 “动态”的含义是 代码生成代理类,一个代理类可以代理多个接口 。 动态区别于 死板 ,静态代理中一个代理类只能代理一个接口,其他不同的接口,就需要再手写不同的代理类,这就很 死板 。 动态代理类似于在安卓里面,我们常

    2024年02月09日
    浏览(31)
  • 代理模式--静态代理和动态代理

    定义:代理模式就是代替对象具备真实对象的功能,并代替真实对象完成相应的操作并且在不改变真实对象源代码的情况下扩展其功能,在某些情况下,⼀个对象不适合或者不能直接引⽤另⼀个对象,⽽代理对象可以在客户端和⽬标对象之间起到中介的作⽤ 使用代理模式可以

    2024年02月15日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包