【动态规划上分复盘】下降路径最小和|礼物的最大价值

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


前言

本文主要讲述动态规划思路的下降路径最小和以及礼物的最大价值两道题。


一、动态规划五部曲

  • 1.确定状态表示(确定dp数组的含义)
  • 2.确定状态转移方程(确定dp的递推公式)
  • 3.确定如何初始化(初始化要保证填表正确)
  • 4.确定遍历顺序
  • 5.返回值

二、下降路径最小和

点我直达
【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode

思路:动态规划解法

  • 1.确定状态表示,即确定dp数组的含义。

    • 写动态规划的题目,确定状态表示是最重要的一步,如何确定呢?往往需要经验+题目描述,就需要大量的动态规划问题基础。
      在本题中,我们需要使用二维dp数组来表示下降路径,所以dp数组的含义是:
      第[i,j]位置的最小下降路径为dp[i][j]。
  • 2.确定状态转移方程(确定递推公式)

    • 根据题目描述,第[i,j]位置是由第[i-1,j-1],[i-1,j],[i-1,j+1]三个位置的任意一个往下走得来,如下图。
      【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode
      所以我们可以确定,dp[i][j]一定与dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]有关。
      我们再回顾dp数组的含义:dp[i][j] :第[i,j]位置的最小下降路径为dp[i][j]
      所以下降到第[i,j]的位置时,一定是由[i-1,j-1],[i-1,j],[i-1,j+1]三个位置的对于的最小dp值+当前位置的路径。
      即:dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+ob[i][j] ,其中ob为题目给出的二维数组。
  • 3.如何初始化

    • 细心的小伙伴会发现,第一行的数据,dp[0][j]是如何推导的呢?如果仅仅开辟题目给出的ob数组大小的dp数组空间,是无法初始化完全的。所以我们给出了一个多开辟虚拟空间的解决方案。如下图:
      【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode
      我们多开一行两列的空间,这样就满足了任意位置都能直接被便利到。
      但开辟虚拟空间需要注意两个问题:
      1.虚拟位置的初始化必须保证原dp数组正确。
      2.注意下标的映射关系。
      • (1)我们应该初始化第一行虚拟空间为0,这样保证了原dp数组的初始化不受影响。
        再初始化第一列和第n+1列为正无穷大。
        【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode

以图中数字为例,第[i-1,j-1]位置,也就是左上角位置是虚拟开辟出来的,所以必须要保证这个位置初始化的时候不能影响原数组的初始化。所以我们应该在这个虚拟位置初始化成正无穷大。就保证永远取不到这个地方。

      • (2)注意下标的映射关系,以上图为例,
        dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+ob[i-1][j-1] ,注意这里是+ob[i-1][j-1]而不是+ob[i][j],因为虚拟数组多开了一行两列,所以整体的元素都往右下角挪了一个位置,所以找原位置是必须回到左上角。
        【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode
  • 4.确定遍历顺序

    • 根据上述描述,和递推公式,可以知道我们只能从上往下进行遍历。
  • 5.返回值

    • 当遍历到最后一行时,我们应该知道,题目要求返回下降路径最小和,在最后一行中,每一个元素都是从上往下的下降路径最小的数,所以我们应该比较这最后一行元素中的最小值,返回即可。

具体代码如下

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& ob) 
    {
        //1.确定dp[i][j]的含义:下降到i,j位置的最小路径为dp[i][j]
        //2.递推公式:
        //dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+ob[i][j]        
        //3.初始化dp数组,多开一行,两列的虚拟空间,全部初始化为0
        //对虚拟空间的要求:1.里面的值要保证后面填表正确
        //2.要注意下标的映射
        //4.遍历顺序,只能从上到下遍历。
        //5.返回值,返回最后一行的最小值
        int n = ob.size();
        vector<vector<int>> dp(n+1,vector<int>(n+2,0));
        for(int i = 1;i<=n;i++)
        {
            dp[i][0] = INT_MAX;
            dp[i][n+1] = INT_MAX;
        }
//        vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
        //第一行全部初始化成0,但是第一列和最后一列的第二行开始,就初始化成正无穷大
        // for(int i = 0;i< n+2;i++)
        // {
        //     dp[0][i] = 0;
        // }

        for(int i = 1;i<= n ;i++)
        {
            for(int j = 1;j<= n;j++)
            {
                dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+ob[i-1][j-1];        
            }
        }
        int ret = INT_MAX;
        //遍历dp表的最后一行,选出最小值
        for(int i = 1;i<=n;i++)
        {
            ret = min(ret,dp[n][i]);
        }
    }
};

时间复杂度O(n^2), 空间复杂度O(n^2)


三、礼物的最大价值

点我直达~

【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode

思路:动态规划

  • 1.状态表示(确定dp数组的含义)
    根据经验和题目描述可知,
    dp[i][j]表示:到达第[i,j]位置拿到的礼物最大价值为dp[i][j].
  • 2.状态转移方程(确定递推公式)
    【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode

由图可知,走到第[i,j]位置一定是由它的上方往下走一步或者它的左侧往右走一步得来。所以dp[i][j]一定跟dp[i-1][j]和dp[i][j-1]有关。
再回顾一下dp数组的含义:到达第[i,j]位置拿到的礼物最大价值为dp[i][j]
那么由此我们可以确定递推公式:
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j],其中grid是题目给出的数组。
可以发现本道题的思路与上一题类似。

  • 3.如何进行初始化
    有了上道题目的经验,我们发现,第一行的元素无法初始化,因为它没有上方的元素和左方的元素。所以我们应该多开辟一行一列的虚拟数组,如下图:
    【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode
    同理:需要注意两个问题,
    1.虚拟位置的初始化必须保证原dp数组正确。
    2.注意下标的映射关系。

所以我们应该初始化成0,这样在虚拟空间不会被选中,对原数组不产生影响。

那么下标的映射关系也是如此:
【动态规划上分复盘】下降路径最小和|礼物的最大价值,每日挠头算法,动态规划,算法,C++,leetcode
假如对想求出图中位置的dp值,应该为:
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1],因为我们多开了一行一列的数组,所以这里原数组整体往右下角移动了一位,要找到原来的值,需要挪动回到左上角查找。

  • 4.确定初始化顺序
    由上面的分析可知,我们应该从上往下初始化,从左往右初始化。

  • 5.返回值

  • 返回右下角的值即可。

具体代码如下:

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) 
    {
        int m = grid.size();
        int n = grid[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-1][j],dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }

};

时间复杂度O(m*n),空间复杂度O(m*n)

总结

今天学到了一个动态规划的点:多开辟一块空间,使得初始化变得更为简单,但是也要注意两个点:
1.虚拟位置的初始化必须保证原dp数组正确。
2.注意下标的映射关系。
文章来源地址https://www.toymoban.com/news/detail-519016.html

到了这里,关于【动态规划上分复盘】下降路径最小和|礼物的最大价值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【动态规划上分复盘】这是你熟悉的地下城游戏吗?

    本文讲解关于动态规划思路的两道题目。 1.确定状态表示(确定dp数组的含义) 2.确定状态转移方程(确定dp的递推公式) 3.确定如何初始化(初始化要保证填表正确) 4.确定遍历顺序 5.返回值 点我直达~ 根据题目可知,每一个位置都对应这三种情况: (d[i][j]由题目给出。)

    2024年02月12日
    浏览(42)
  • 【C】动态规划 之 多维最大最小路径和

    总结一下这类题型的思路: 每一步所求的最优解 = 上一步的最优解 + 这一步的情况 主要思路: 1.到达每一个位置的 最大和 等于 前一步最大和 加上 这一位置的值, 而前一步要么是从左上下来,要么是从右上下来,这样就将原问题分解了 2.记得初始化dp数组,不然里面元素初

    2024年04月27日
    浏览(42)
  • 【学会动态规划】礼物的最大价值(7)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:剑指 Offer 47. 礼物的最大价值

    2024年02月16日
    浏览(37)
  • Java 动态规划 剑指 Offer 47. 礼物的最大价值

     代码展示:         进行动态规划的五个步骤:         1.状态表示                 dp[i][j]表示从起点到[i][j]这个位置上能获得礼物的最大价值         2.状态转移方程                 我们分析距离[i][j]最近的位置,根据题意我们到达[i][j]位置只能从[i-1][j]向下移动或

    2024年02月13日
    浏览(39)
  • 剑指offer(C++)-JZ47:礼物的最大价值(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 在一个mtimes nm×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向

    2024年02月05日
    浏览(63)
  • leetcode刷题(轮转数组、买股票的最佳时机、买卖股票的最佳时机2、跳跃游戏、跳跃游戏2、最大子序列交替和、交替数字和、下降路径最小和)

    目录 1、轮转数组 2、买卖股票的最佳时机 3、买卖股票的最佳时机② 4、跳跃游戏 5、跳跃游戏2 6、最大子序列交替和 7、交替数字和 8、下降路径最小和 1、轮转数组 2、买卖股票的最佳时机 3、买卖股票的最佳时机② 4、跳跃游戏 5、跳跃游戏2 6、最大子序列交替和 7、交替数

    2024年02月16日
    浏览(31)
  • 【学会动态规划】最小路径和(9)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:64. 最小路径和 - 力扣(Leet

    2024年02月16日
    浏览(35)
  • Java 动态规划 64. 最小路径和

      代码展示:  dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];  该题可以通过动态规划解决,动态规划的题根据以下的5大步骤便可轻松解决         1.状态表示                 题目要求我们计算从起点到最后一个位置的最小路径和,我们可以创建一个dp表,dp【i】【j】表示从

    2024年02月13日
    浏览(43)
  • 动态规划问题——矩阵的最小路径和

    题目: 给定一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有路径中最小的路径和。 示例: 给定的m如下: 1        3         5        9 8        1        3        4  5        0        6 

    2023年04月08日
    浏览(49)
  • 最小路径和-力扣64-java 动态规划

    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。 示例 2: 输入:grid = [[1,

    2023年04月09日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包