动态规划Dynamic Programming

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

动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java

 上篇文章我们简单入门了动态规划(一般都是简单的上楼梯,分析数据等问题)点我跳转,今天给大家带来的是路径问题,相对于上一篇在一维中摸爬滚打,这次就要上升到二维解决问题,但都用的是动态规划思想嘛,所以大差不差,且听我慢慢道来。
还是用一样的方法,用同样的分析思路和技巧来分析问题解决问题。
路径规划
不同路径
动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java

  • 状态表示
     这道题我们需要知道的是从左上角位置走到右下角位置总共有多少的路径,我们可以将问题拆分,题目中所说,机器人每次只能向下或者向右移动一步,所以我们到达右下角位置是怎么到达的呢?
    如图
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java所以到达目标的方法就是到达这两个位置方法的总和。
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
    因此这道题的状态表示就是到达ij位置总共的方法数。
  • 状态转移方程
    有了上边的分析,我们可以很清晰地知道
    状态转移方程为

dp[i][j]=dp[i-1][j]+dp[i][j-1]

  • 初始化
     初始化顺序即填表顺序是从左上角到右下角,但是我们应该怎么初始化呢?如果套用我们的状态转移方程,我们会发现在数租的边缘部分一定会遇到越界的情况。
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
     所以在初始化时,我们可以将数组多开一行一列,这样就可以解决越界访问的问题,如何初始化这个表格呢?我们来试着分析。
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
    其他位置全部初始化为0,这样就可以避免多开的数组影响我们后续的得到的结果。
  • 填表顺序
    填表顺序就是从左上角向左下角进行填写。
  • 返回值
    很简单,就是返回填表后到达i,j位置时的值即可
    接下来我们就可以根据分析出的结论写代码了。

class Solution {
public:
    int uniquePaths(int m, int n) {
        //new出一个二维数组,并将他们的值初始化为0
        vector<vector<int>> dp(m+1,vector<int>(n+1));//这里应该怎么给空间啊
        dp[0][1]=1;
        for(int i=1;i<=m;i++)//先填每一行
            for(int j=1;j<=n;j++)//再填每一列  
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        
        return dp[m][n];
    }
};

动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
这里还有一道十分相仿的题目,多了一步扩展的思维而已,尝试一下吧!
不同路径2


第二道题
珠宝的最高价值

动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
 如果说上一道题对标的是上一篇中的上楼梯的方法数,那么这道题对标的就是上楼梯最小花费。
思路和上一道题目很像,一起来看一看。

  • 状态表示
     同样要创建一个二维数组,到达ij位置可以拿到的珠宝价值最高,那么状态表示就是到达ij位置能拿到的最大珠宝价值,说白了就是所以路径中求和最大的一条路径。
  • 状态转移方程
     移动方式和上一道题目一样,但是相比于上一道题目的相加,这道题目就是从上边或者左边到达ij位置时,他们两个谁的路径和最大。因为上一道题目已经解释很清楚了,这里就不再画图赘述。

dp[i][j]=max(dp[i-1][j],dp[i][j-1];

  • 填表顺序
     从左上角向右下角。要注意是从下表为1,1位置开始填表的。
  • 初始化
     初始化方式和前边那道题目大同小异,只不过我们多开的数组默认为0不用管就行,因为第一个位置只需要加上他这个位置的财宝价值即可。
  • 返回值
    返回到达左下角位置能达到的最高价值数。
    我们还是直接来展示代码吧,毕竟和前边那道题很像,除了状态转移方程不同。
    代码如下
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m=frame.size();
        int n=frame[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=max(dp[i][j-1],dp[i-1][j])+frame[i-1][j-1];

        return dp[m][n];
    }
};

动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
第三道题
下降路径最小和
动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
 首先来进行题目解析,这道题目只需要从上到下找到最小的路径即可,而且在某位置可以向下边三个位置进行跳转。

  • 状态表示
     状态表示就是到达ij位置时,需要的最小路径和,然后找出最后一行中最小的,就找到了最小路径下降和。
  • 状态转移方程
    可以来画图分析一下
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
     根据我们的状态表示,我们需要找到最小路径和,只需要找到这个位置上边三种情况的最小路径和即可。
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
    当然,到达ij位置时,还需要加上ij位置上的值。
    故而状态转移方程为

dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j+1],dp[i-1][j]))+matrix[i-1][j-1];//要注意这里位置的对应

这里状态对应的问题后边会解释到。

  • 初始化
    这里初始化是一个问题,问题在于在我们求第一行时,第一行的上边并没有数据,访问dp[-1][-1]势必会造成越界访问,如何解决呢?有了上边题目的铺垫,只需要扩展数组即可。
    相信大家已经看到了上边的画图中分别用两种颜色标记,如何初始化才能不影响后续的结果呢?
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
     因为这道题目的数组开的并不规则,所以对应位置容易混淆,如果你匆匆写代码的话,势必会出现这样的问题,
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
    还会出现这样的问题
    动态规划Dynamic Programming,刷题笔记,动态规划,算法,c++,开发语言,c语言,java
     第一种就是没有空控制好dp表的填写,导致初始化时的INT_MAX参与了运算,第二种就是因为多开两列,多开一行导致的位置判断不准确,以至于越界访问了。

  • 填表顺序
    很明显,从上往下进行填表

  • 返回值
     这里返回值和之前不太一样,需要找到最后一行元素中最小的一个,然后返回即可。
     代码如下,一定要尝试自己写一下,这道题是正方形表格,但是我作为长方形表格来做了,大家可以忽略这些小细节哈。

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>> dp(m+1,vector<int> (n+2,INT_MAX));
        //怎么把两边初始化为int_max;
        //cout<<int_max;
        for(int k=0;k<=n+1;k++)
        {
            dp[0][k]=0;
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n+1;j++)//这里要注意,只需要初始化我们需要的部分
            {
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j+1],dp[i-1][j]))+matrix[i-1][j-1];//要注意这里位置的对应
            }
        }
        //此时只需找到最后一行的最小值。
        int ret=INT_MAX;
        for(int j=1;j<=n;j++)
        {
            ret=min(ret,dp[m][j]);
        }
        return ret;
    }
};

 本文到此结束,感谢大家观看,有问题及时提出,我会积极解决的。文章来源地址https://www.toymoban.com/news/detail-843934.html

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

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

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

相关文章

  • 【数据结构】动态规划(Dynamic Programming)

    求解决策过程(decision process)最优化的数学方法。 将多阶段决策过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。 与分治法类似,将待求解问题 分解成若干个子问题 。 但是经分解得到的子问题往往 不是相互独立 的。 如果使用分治法求解问题,有些子问

    2024年02月03日
    浏览(12)
  • 动态规划算法刷题笔记【状压dp】

    a1 == 1 判断是否为奇数,如果为1,则为奇数 因为奇数二进制末位一定是1,所以 与1 得到的结果是1 这里,114——2 14 ——第15位是1,可以表示14个1 i(1j)—— 从0开始是因为,原本第1位就是1。所以j=0时,对应的就是 i 的最低位 F l o y d Floyd Fl oy d 算法: n o w ∣ f l a g = = f l

    2024年02月11日
    浏览(9)
  • ​Python—数据结构与算法​---动态规划—DP算法(Dynamic Programing)

    目录 我们一路奋战, 不是为了改变世界, 而是为了不让世界改变我们。 动态规划——DP算法(Dynamic Programing) 一、🏔斐波那契数列(递归VS动态规划) 1、🐒斐波那契数列——递归实现(python语言)——自顶向下 2、🐒斐波那契数列——动态规划实现(python语言)——自底

    2024年02月10日
    浏览(10)
  • 动态规划算法OJ刷题(3)

    问题描述 给出一个字符串s,分割s使得分割出的每一个子串都是回文串。计算将字符串s分割成回文串的最小切割数。例如:给定字符串s=“aab”,返回1,因为回文分割结果[“aa”,“b”]是切割一次生成的。 解题思路 方法1:用一维数组来完成,O(N^3) 注意转移方程必须是让两个

    2024年02月14日
    浏览(6)
  • 算法设计与分析-Dynamic Programming「国科大」卜东波老师

    A robber is planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. (a) Given a list of non-negative integers

    2024年02月22日
    浏览(12)
  • 算法刷题打卡049 | 动态规划17

    动态规划终于要刷完了!虽然动规五部曲已经烂熟,也刷了有二三十题经典的动态规划题,但是自己实际做题时未必能用的很好,一方面是有些题目实在很难想到用动规解题,另一方面是即使想到动态规划,往往卡在状态的定义和状态转移上(更别说一些细节了,比如初始化

    2023年04月15日
    浏览(6)
  • 力扣刷题-动态规划算法3:完全背包问题

    问题描述: 1)有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 2) 每件物品都有无限个(也就是可以放入背包多次) (比0-1背包多出的条件) 3) 求解将哪些物品装入背包里物品价值总和最大。 求解步骤: 1)首先遍历物品,然

    2023年04月13日
    浏览(18)
  • 动态规划01背包问题-代码随想录-刷题笔记

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

    2024年02月07日
    浏览(7)
  • OJ刷题---[算法课动态规划]走网格(C++完整代码)

    m行n列的网格,从左上角(1,1)出发,每一步只能向下或者向右,问共有多少种方法可以走到右下角(m,n); 输入参数 m n (1=m=10 1=n=10) 输出多少种走法 比如: 输入:2 3 输出:3 输入:5 5 输出:70 完整代码(C++): 结果: 注意:最后调用的时候,是调用sum(m,n),而不是sum(m+1

    2024年02月07日
    浏览(7)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(12)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包