leetcode64 最小路径和

蔚落 2023-06-16 10:34 19阅读 0赞

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

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

示例:

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

思路：

grid\[i\]\[j\]更新为走到grid\[i\]\[j\]的最小代价。

只能从左边走过来，或者从上边走过来，答案为两种情况中较小的加上本身。

注意：初始化，第一行第一列只有一种方法走过来。

class Solution {
        public int minPathSum(int[][] grid) {
            int len1=grid.length;
            int len2=grid[0].length;
            int i,j;
            for(i=1;i<len1;++i)grid[i][0]+=grid[i-1][0];
            for(i=1;i<len2;++i)grid[0][i]+=grid[0][i-1];
            for(i=1;i<len1;++i)
                for(j=1;j<len2;++j)
                    grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
            return grid[len1-1][len2-1];
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191125205745530.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode 64：最小路径和

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

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

相关 LeetCode-64. 最小路径和

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

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

相关 LeetCode 64. 最小路径和

题目链接[https://leetcode.cn/problems/minimum-path-sum/description/][https_leetcode.cn_probl

ゝ一纸荒年。/ 2024年02月19日 10:07/ 0 赞/ 29 阅读

相关 leetcode64 最小路径和

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

蔚落/ 2023年06月16日 10:34/ 0 赞/ 20 阅读

相关 Leetcode 64. 最小路径和

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

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

相关 LeetCode64 最小路径和

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

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

相关 64. 最小路径和

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

朱雀/ 2022年10月10日 01:48/ 0 赞/ 153 阅读

相关 leetcode64最小路径和

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

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

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

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

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

相关 leetcode:64. 最小路径和

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

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