Leetcode刷题详解——下降路径最小和

这篇具有很好参考价值的文章主要介绍了Leetcode刷题详解——下降路径最小和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 题目链接:931. 下降路径最小和

2. 题目描述:

给你一个 n x n方形 整数数组 matrix ,请你找出并返回通过 matrix下降路径最小和

下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)(row + 1, col) 或者 (row + 1, col + 1)

示例 1:

Leetcode刷题详解——下降路径最小和,leetcode,算法,职场和发展

输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:如图所示,为和最小的两条下降路径

示例 2:

Leetcode刷题详解——下降路径最小和,leetcode,算法,职场和发展

输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:如图所示,为和最小的下降路径

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

3. 解法(动态规划):

3.1算法思路:

3.1.1 状态表示:

dp[i][j]表示:到达[i,j]位置时,所有下降路径中的最小和

3.1.2 状态转移方程:

到达 [i,j]位置可能有三种情况:

Leetcode刷题详解——下降路径最小和,leetcode,算法,职场和发展

我们要的是三种情况下的最小值,然后加上矩阵在[i,j]位置

于是dp[i,j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i,j]

3.1.3 初始化

可以在最前面加上一个辅助结点,进行初始化。使用这种技巧需要注意两点:

  1. 辅助结点里面的值要保证后续填表是正确的

  2. 下标的映射关系

  3. 在本题中,需要加上一行,并且加上两列。所有位置都初始化为无穷大,然后将第一行初始化为0即可

Leetcode刷题详解——下降路径最小和,leetcode,算法,职场和发展

3.1.4 填表顺序

从上往下

3.1.5 返回值

注意这里不是返回dp[m][n]的值

题目要求:【只要到达最后一行】,因此这里应该返回【dp表最后一行的最小值】文章来源地址https://www.toymoban.com/news/detail-717618.html

3.2 C++算法代码:

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n=matrix.size();
        //创建dp表
        vector<vector<int>>dp(n+1,vector<int>(n+2,INT_MAX));
        //初始化第一行
        for(int j=0;j<n+2;j++) dp[0][j]=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]))+matrix[i-1][j-1];
            }
        }
        int ret=INT_MAX;
        for(int j=0;j<=n;j++)
        {
            ret=min(ret,dp[n][j]);
        }
        //返回结果
        return ret; 
    }
};

到了这里,关于Leetcode刷题详解——下降路径最小和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode每日一题:1289. 下降路径最小和 II(2023.8.10 C++)

    目录 1289. 下降路径最小和 II 题目描述: 实现代码与解析: 动态规划 原理思路:         给你一个  n x n  整数矩阵  grid  ,请你返回  非零偏移下降路径  数字和的最小值。 非零偏移下降路径  定义为:从  grid  数组中的每一行选择一个数字,且按顺序选出来的数字

    2024年02月13日
    浏览(37)
  • Leetcode刷题详解——长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 提示: 1 = target = 109 1 = nums.length

    2024年02月07日
    浏览(47)
  • 算法leetcode|64. 最小路径和(rust重拳出击)

    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明 :每次只能向下或者向右移动一步。 m == grid.length n == grid[i].length 1 = m, n = 200 0 = grid[i][j] = 200 面对这道算法题目,二当家的再次陷入了沉思。 这道题和62. 不同

    2024年02月15日
    浏览(44)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(48)
  • 算法学习——LeetCode力扣补充篇11(64. 最小路径和、48. 旋转图像 、169. 多数元素、394. 字符串解码、240. 搜索二维矩阵 II )

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

    2024年04月23日
    浏览(37)
  • 【LeetCode】64.最小路径和

    给定一个包含非负整数的  m  x  n  网格  grid  ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明: 每次只能向下或者向右移动一步。 示例 1: 示例 2: 提示: m == grid.length n == grid[i].length 1 = m, n = 200 0 = grid[i][j] = 200 又是一道动态规划,这次也是

    2024年02月15日
    浏览(33)
  • 【LeetCode】最小路径和

    链接: 最小路径和 题目描述 算法流程 编程代码

    2024年02月14日
    浏览(40)
  • Leetcode.1631 最小体力消耗路径

    Leetcode.1631 最小体力消耗路径 Rating : 1948 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ,其中 heights[row][col] 表示格子 ( r o w , c o l ) (row, col) ( ro w , co l ) 的高度。一开始你在最左上角的格子 ( 0 , 0 ) (0, 0) ( 0 , 0 ) ,且你希望去最右下角的格子 ( r o w s − 1

    2023年04月14日
    浏览(33)
  • 【leetcode刷题】66.使用最小花费爬楼梯——Java版

    ⭐欢迎订阅《leetcode》专栏,每日一题,每天进步⭐ 我觉得这个题的描述应该改改:每个阶梯都有一定数量坨屎,一次只能跨一个或者两个阶梯,走到一个阶梯就要吃光上面的屎,问怎么走才能吃最少的屎?开局你选前两个阶梯的其中一个作为开头点,并吃光该阶梯的屎。

    2023年04月08日
    浏览(78)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包