64. 最小路径和

朱雀 2022-10-10 01:48 139阅读 0赞

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

class Solution {
        public int minPathSum(int[][] grid) {
            /**
            动态规划  
            第一行的最小路径和只能有向右而来 所以累加  
            第一列也是如此
             */
             int [][] dp=new int[grid.length][grid[0].length];
             dp[0][0]=grid[0][0];//到当前方块(包含当前方块)的最小路径和
             for(int i=1;i<grid.length;i++){
                 dp[i][0]+=(dp[i-1][0]+grid[i][0]);
             }
    
             for(int j=1;j<grid[0].length;j++){
                 dp[0][j]+=(dp[0][j-1]+grid[0][j]);
             }
    
             for(int i=1;i<grid.length;i++){
                 for(int j=1;j<grid[0].length;j++){
                     dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                 }
             }
            
             return  dp[grid.length-1][grid[0].length-1];
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/496baae40f784ada87b21af64b14779d.png

发表评论取消回复

表情：

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

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

相关阅读

相关 64. 最小路径和

64. 最小路径和给定一个包含非负整数的 m ∗ n m \ n m∗n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每

不念不忘少年蓝@/ 2024年03月26日 16:45/ 0 赞/ 72 阅读

相关最小路径和

最小路径和 1、参考资料 https://leetcode-cn.com/problems/minimum-path-sum/ 2、题目要求 > 题目描述

快来打我*/ 2022年12月05日 10:25/ 0 赞/ 125 阅读

相关 LeetCode64 最小路径和

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

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

相关 64. 最小路径和

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

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

相关 leetcode64最小路径和

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

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

相关三角形最小路径和

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

偏执的太偏执、/ 2022年05月17日 08:14/ 0 赞/ 184 阅读

相关 LeetCode 64.Minimum Path Sum (最小路径和)

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

女爷i/ 2022年05月10日 05:40/ 0 赞/ 167 阅读

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

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

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

相关 leetcode:64. 最小路径和

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

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

相关 LeetCod: 64. Minimum Path Sum 最小路径和

试题： Given a m x n grid filled with non-negative numbers, find a path from top left to

迷南。/ 2021年06月24日 16:10/ 0 赞/ 295 阅读