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

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

目录

1289. 下降路径最小和 II

题目描述:

实现代码与解析:

动态规划

原理思路:


1289. 下降路径最小和 II

题目描述:

        给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为:从 grid 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

示例 1:

Leetcode每日一题:1289. 下降路径最小和 II(2023.8.10 C++),Leetcode,leetcode,c++,算法

输入:grid = [[1,2,3],[4,5,6],[7,8,9]]
输出:13
解释:
所有非零偏移下降路径包括:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ,所以答案是 13 。

示例 2:

输入:grid = [[7]]
输出:7

提示:

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • -99 <= grid[i][j] <= 99

实现代码与解析:

动态规划

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {

        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n,vector<int>(m, 0x3f3f3f3f));

        for (int i = 0; i < m; i++)
            f[0][i] = grid[0][i];

        for (int i = 1; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < m; k++)
                {
                    if (j == k) continue;
                    f[i][j] = min(f[i][j], f[i - 1][k] + grid[i][j]);
                }
        int res = 0x3f3f3f3f;
        for (int i = 0; i < m; i++)
            res = min(res, f[n - 1][i]);
        // for (int i = 0; i < n; i++)
        // {
        //     for (int j = 0; j < m; j++)
        //     {
        //         cout << f[i][j] << " ";
        //     }
        //     cout << endl;
        // }      
        return res;
    }
};

原理思路:

        顶多中等题,难度不应该标困难。

        动态规划,dp数组含义就是到以下标 i, j 为结尾的最小值。数据量很小,其实就是三重暴力循环而已。 文章来源地址https://www.toymoban.com/news/detail-646997.html

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

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

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

相关文章

  • 2023-07-30 LeetCode每日一题(环形链表 II)

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

    2024年02月15日
    浏览(60)
  • 2023-09-10 LeetCode每日一题(课程表 II)

    点击跳转到题目位置 现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。 返回你为了学完所

    2024年02月09日
    浏览(49)
  • 2023-08-04 LeetCode每日一题(不同路径 III)

    点击跳转到题目位置 在二维网格 grid 上,有 4 种类型的方格: 1 表示起始方格。且只有一个起始方格。 2 表示结束方格,且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方

    2024年02月14日
    浏览(42)
  • 2023-09-05 LeetCode每日一题(从两个数字数组里生成最小数字)

    点击跳转到题目位置 给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ,每个数组中的元素 互不相同 ,请你返回 最小 的数字,两个数组都 至少 包含这个数字的某个数位。 示例 1: 示例 2: 提示: 1 = nums1.length, nums2.length = 9 1 = nums1[i], nums2[i] = 9 每个数组中,元素 互不相

    2024年02月09日
    浏览(60)
  • Leetcode每日一题:167. 两数之和 II - 输入有序数组(2023.7.8 C++)

    目录 167. 两数之和 II - 输入有序数组 题目描述: 实现代码与解析: 暴力(超时) 双指针 原理思路: 二分 原理思路:         给你一个下标从  1  开始的整数数组  numbers  ,该数组已按   非递减顺序排列   ,请你从数组中找出满足相加之和等于目标数  target  的两

    2024年02月13日
    浏览(47)
  • Leetcode刷题详解——下降路径最小和

    给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的 下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素

    2024年02月08日
    浏览(42)
  • (贪心) 剑指 Offer 14- II. 剪绳子 II ——【Leetcode每日一题】

    难度:中等 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段( m 、 n 都是整数, n 1 并且 m 1 ),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最

    2024年02月13日
    浏览(49)
  • (动态规划) 132. 分割回文串 II ——【Leetcode每日一题】

    难度:困难 给你一个字符串 s ,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2: 输入:s = “a” 输出:0 示例 3: 输入:

    2024年02月15日
    浏览(46)
  • leetcode每日一题——45.跳跃游戏II(面试经典150题)

    45. 跳跃游戏 II - 力扣(LeetCode) 给定一个长度为 n 的 0 索引 整数数组 nums。 初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:   0 = j = nums[i]     i + j n 返回到达 nums[n - 1] 的最小跳跃次数

    2024年02月13日
    浏览(44)
  • ( 数组和矩阵) 667. 优美的排列 II ——【Leetcode每日一题】

    难度:中等 给你两个整数 n 和 k ,请你构造一个答案列表 answer ,该列表应当包含从 1 到 n 的 n 个不同正整数,并同时满足下述条件: 假设该列表是 answer = [a1, a2, a3, ... , an] ,那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。 返回列表 answer

    2024年02月06日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包