一文读懂动态规划问题

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

动态规划五部曲

动态规划,英文: Dynamic Programming, 简称DP,如果某一个问题由很多重叠子问题,使用动态规划是最有效的。

所谓动态规划就是,在解决一个问题的过程中,将其分解为很多个小的部分,环环相扣。最典型的一个例子,我们入门编程时都学习过的斐波那契数,每个数都是由前面的两个数字推导出来的,也就是所谓的前一个状态。

动态规划解题步骤

在我刚接触动规题目的时候,比如说做01背包的问题,去把状态转移公式背下来,然后照着这样去改改开始写代码,把题目做完之后可能都不知道后一个状态是如何推导而来的。

对于动态规划的问题,如果我们在分析题目的时候能够看出来可以转换为动态规划来求解的话一般就比较好解决了。对于此类问题我一般拆解为五步。简称动归五部曲

1.确定dp数组 以及其下标的含义

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

在这里我给个建议,就是在做题的时候在我们把dp数组推导出来后,去将它打印出来,看看究竟是不是按照自己的思路推导的!就算出现问题的时候我们也可以很直观的看出来问题出在哪里,当出现错误的时候不要去胡乱的修改,先去分析以上的五步到底是哪里出了问题,有没有真正理解dp数组的含义。

实战演练

  1. 爬楼梯

一文读懂动态规划问题,题解,动态规划,算法

如果没有接触过的话乍一看会感觉没有思路,既然每次只能爬1或2层台阶,爬到第一层楼有一种方法,爬到第二层楼就是有两种方法(直接爬两层或者分为两次一次爬一层),如何与动态规划结合起来呢,既然一次只能爬1或2层,那么不管是哪层楼,是不是只能由它的前一层或前两层爬过来。

分析到这里我们按照前面讲的动归五部曲:

1.确定dp数组以及下标的含义

dp[i]就是爬到第i层楼有dp[i]种方法

2.确定递推公式

不管哪一层楼都只能由它的前一层或前两层爬过来,那么很简单

dp[i] = dp[i-1]+dp[i-2].

在推导的时候,要时刻想着dp[i]的含义。

3.dp数组如何初始化

dp[i]的含义是爬到第i层楼,有dp[i]种方法。那么本题中我们应该从哪里开始遍历呢,dp[0]有没有含义呢,很明显的就可以得到dp[1] = 1;dp[2] = 2 那么根据状态转移方程,是不是要将dp[0]初始化为1呢,这显然是不正确的。因为我们初始状态就是在第0层,也就是说dp[0]是没有意义的,所以在这道题中 应该初始化dp[1] = 1,dp[2] = 2.

4.遍历顺序

我们已经将dp[1]和dp[2]初始化后,那么就是从第三层楼开始遍历,一直推导到我们所需要求的楼层。

5.举例推导dp数组

前面我们已经说了,在推导过程中将每一个状态都打印出来,我们可以举例推导dp[3] = 3,都是符合的,所以本题到这里按照五部曲已经解决。当我们熟悉了这个过程之后是非常快的。

class Solution {
public:
    int climbStairs(int n) {
        //1. 确定dp数组的含义 dp[i] 表示爬到第i层楼一共有多少种方法
        //2. 确定递推公式 dp[i] = dp[i-1] + dp[i-2];
        //3. dp数组初始化  dp[1] = 1, dp[2] = 2
        //4. 遍历顺序 从第3层楼开始遍历
        //5. 举例推导验证
        vector<int> dp(n+1);
        if(n<=1) return n;
        dp[1] = 1,dp[2] = 2;
        for(int i= 3;i<=n;i++ )
        {
            dp[i] = dp[i-1]+dp[i-2];
        }  
        return dp[n];
        
​
    }
};

以上就是对于动态规划问题的基本阶梯思路 后续还会在本帖中更新相关动态规划问题的题解。文章来源地址https://www.toymoban.com/news/detail-857871.html

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

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

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

相关文章

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

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,如果给算法的难度和复杂度排一个排名,那么动态规划算法一定名列前茅。在最开始没有什么整体的方法的时候,我也曾经被动态规划折磨过很长时间,通过我一段时间的刷题

    2024年02月05日
    浏览(42)
  • 【算法专题】动态规划之路径问题

    题目链接 - Leetcode -62.不同路径 Leetcode -62.不同路径 题目:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示

    2024年01月24日
    浏览(47)
  • 【算法-动态规划】0-1 背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(43)
  • 算法沉淀 —— 动态规划篇(路径问题)

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

    2024年04月17日
    浏览(42)
  • 【算法 - 动态规划】找零钱问题Ⅲ

    在前面的动态规划系列文章中,关于如何对递归进行分析的四种基本模型都介绍完了,再来回顾一下: 从左到右模型 : arr[index ...] 从 index 之前的不用考虑, 只考虑后面的该如何选择 。 范围尝试模型 :思考 [L ,R] 两端,即 开头和结尾 处分别该如何取舍。 样本对应模型 :

    2024年04月09日
    浏览(41)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(48)
  • 【算法】动态规划中的路径问题

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,如果给算法的难度和复杂度排一个排名,那么动态规划算法一定名列前茅。今天,我们通过由简单到困难的两道题目带大家学会动态规划中的路径问题 好了废话不多说,开始我

    2024年02月05日
    浏览(38)
  • 算法学习17-动态规划01:背包问题

    提示:以下是本篇文章正文内容: 提示:这里对文章进行总结: 💕💕💕

    2024年04月27日
    浏览(49)
  • C++算法 —— 动态规划(2)路径问题

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月06日
    浏览(48)
  • 【算法优选】 动态规划之路径问题——贰

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的

    2024年02月05日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包