leetcode:64. 最小路径和

深碍√TFBOYSˉ_ 2022-04-05 17:48 151阅读 0赞

## 题目: ##

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

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

示例:

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

## 分析: ##

dp

## 代码: ##

public int minPathSum(int[][] grid) {
    		if (grid == null || grid.length == 0 || grid[0].length == 0) {
    			return 0;
    		}
    		int m = grid.length;
    		int n = grid[0].length;
    
    		for (int i = 0; i < m; i++) {
    			for (int j = 0; j < n; j++) {
    				if (i == 0 && j == 0) {
    					continue;
    				} else if (i == 0) {
    					grid[i][j] += grid[i][j - 1];
    				} else if (j == 0) {
    					grid[i][j] += grid[i - 1][j];
    				} else {
    					grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    				}
    			}
    		}
    
    		return grid[m - 1][n - 1];
    
    	}

## 效率: ##

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

## 总结: ##

dp

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220405/862e0d70523445e58b9e67b5592c9f0f.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode 64：最小路径和

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

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

相关 64. 最小路径和

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

不念不忘少年蓝@/ 2024年03月26日 16:45/ 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 赞/ 11 阅读

相关 LeetCode64 最小路径和

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

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

相关 64. 最小路径和

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

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

相关 leetcode64最小路径和

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

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

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

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

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

相关 leetcode:64. 最小路径和

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

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

相关 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 赞/ 280 阅读