2023-07-13 LeetCode每日一题(下降路径最小和)

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

2023-07-13每日一题

一、题目编号

931. 下降路径最小和

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

提示:

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

四、解题代码

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int dp[m+1][n+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                dp[i][j] = INT_MAX;
            }
        }
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i == 0){
                    dp[i][j] = matrix[i][j];
                    continue;
                }
                if(j - 1 >= 0){
                    dp[i][j] = min(dp[i][j], matrix[i][j] + dp[i-1][j-1]);    
                }
                dp[i][j] = min(dp[i][j], matrix[i][j] + dp[i-1][j]);
                if(j + 1 < n){
                    dp[i][j] = min(dp[i][j], matrix[i][j] + dp[i-1][j+1]);
                }
            }
        }
        int min0 = INT_MAX;
        for(int i = 0; i < n; ++i){
            min0 = min(min0, dp[m-1][i]);
        }
    return min0;
    }
};

五、解题思路

(1) 本道题目通过动态规划算法来解决问题。

(2) 首先设置状态,dp[i][j] 代表的是到达(i,j)位置的下降路径最小和 。定义初始状态,第一行的所有下降路径最小和都是对应矩阵的值。

(3) 题目给出了每一个状态怎么转移过来,根据题目的提示进行状态转移,通过循环递推即可。

(4) 最后返回最后一行的最小值,即为下降路径最小和文章来源地址https://www.toymoban.com/news/detail-555027.html

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

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

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

相关文章

  • 2023-07-15 LeetCode每日一题(四数之和)

    点击跳转到题目位置 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且 不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 = a, b, c, d n a、b、c 和 d 互不相同 nums[a] + nums[b]

    2024年02月16日
    浏览(46)
  • 2023-07-08 LeetCode每日一题(三数之和)

    点击跳转到题目位置 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 提示: 3 = nums.length = 3000 -10 5

    2024年02月13日
    浏览(50)
  • 2023-07-29 LeetCode每日一题(环形链表)

    点击跳转到题目位置 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:p

    2024年02月15日
    浏览(41)
  • 2023-07-31 LeetCode每日一题(重排链表)

    点击跳转到题目位置 给定一个单链表 L 的头节点 head ,单链表 L 表示为: 请将其重新排列后变为: 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: 示例 2: 提示: 链表的长度范围为 [1, 5 * 10 4 ] 1 = node.val = 1000 (1) 使用 分治 的思路来解决问题。

    2024年02月14日
    浏览(46)
  • 2023-07-28 LeetCode每日一题(并行课程 III)

    点击跳转到题目位置 给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。同时给你一个二维整数数组 relations ,其中 relations[j] = [prevCourse j , nextCourse j ] ,表示课程 prevCoursej 必须在课程 nextCourse j 之前 完成(先修课的关系)。同时给你一个下标从 0 开始的整数数组 time ,其

    2024年02月15日
    浏览(48)
  • 2023-07-30 LeetCode每日一题(环形链表 II)

    点击跳转到题目位置 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链

    2024年02月15日
    浏览(60)
  • LeetCode 每日一题 2023/8/7-2023/8/13

    记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 8/7 344. 反转字符串 双指针 8/8 1749. 任意子数组和的绝对值的最大值 记录最小值 最大值 8/9 1281. 整数的各位积和之差 按要求计算 8/10 1289. 下降路径最小和 II 从上到下遍历每一行 在每一

    2024年02月13日
    浏览(50)
  • 2023/07/01_leetcode每日一题_1. 两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 一开始审错题了,还以

    2024年02月12日
    浏览(52)
  • 2023/07/02_leetcode每日一题_2.两数相加

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例: 输入:l1 = [9,9,9,9,9,9

    2024年02月11日
    浏览(48)
  • 2023-08-13 LeetCode每日一题(合并两个有序数组)

    点击跳转到题目位置 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 **注意:**最终,合并后数组不应由函数返回,而是存储在数组 num

    2024年02月13日
    浏览(59)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包