LeetCode：最小路径和

向右看齐 2024-04-17 06:07 28阅读 0赞

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
    [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 7
    解释: 因为路径 1→3→1→1→1 的总和最小。

// 动态规划方程: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
    //当然还要考虑边界条件，即i == 0 和 j == 0的情况
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int m = grid.size();
            int n = grid[0].size();
            vector<vector<int>> dp(m, vector<int>(n));
            for(int i = 0; i < grid.size(); i++)
            {
                for(int j = 0; j < grid[0].size(); j ++)
                {
                    if(i == 0 && j == 0)
                        dp[i][j] = grid[i][j];
                    else if(i == 0 )
                        dp[i][j] = grid[i][j] + dp[i][j-1];
                    else if(j == 0)
                        dp[i][j] = grid[i][j] + dp[i-1][j];
                    else  
                        dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
                }
            }
            return dp[m-1][n-1];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode：最小路径和

定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例: 输入:...

向右看齐/ 2024年04月17日 06:07/ 0 赞/ 29 阅读

相关 LeetCode 64：最小路径和

[链接][Link 1] 题目： ![在这里插入图片描述][745a2278e146425ea94228d9b4625eaf.png] 思路：dp 定义备忘录m

﹏ヽ暗。殇╰゛Y/ 2024年04月08日 12:56/ 0 赞/ 35 阅读

相关 LeetCode-64. 最小路径和

目录动态规划题目来源 [64. 最小路径和][64.] 动态规划 1.确定dp数组以及下标的含义定义 dp\[i\]\[j\] 为

╰+攻爆jí腚メ/ 2024年03月24日 16:40/ 0 赞/ 13 阅读

相关 Leetcode 64. 最小路径和

Leetcode 64. 最小路径和 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

布满荆棘的人生/ 2023年02月14日 02:56/ 0 赞/ 10 阅读

相关 LeetCode64 最小路径和

题目重述给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

素颜马尾好姑娘i/ 2022年10月14日 01:17/ 0 赞/ 103 阅读

相关 leetcode64最小路径和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

秒速五厘米/ 2022年09月05日 04:05/ 0 赞/ 110 阅读

相关 LeetCode-64 最小路径和（dp）

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例: 输入:

短命女/ 2022年04月24日 02:44/ 0 赞/ 141 阅读

相关 leetcode 120. 三角形最小路径和

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

朱雀/ 2022年04月13日 09:50/ 0 赞/ 160 阅读

相关 leetcode:64. 最小路径和

题目: 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例: 输入

深碍√TFBOYSˉ_/ 2022年04月05日 17:48/ 0 赞/ 151 阅读

相关【Leetcode】120.三角形最小路径和

题目给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定三角形： [ [2], [

旧城等待，/ 2022年01月20日 11:55/ 0 赞/ 208 阅读