LeetCode64. 给定一个包含非负整数的 m × n 网格 grid,请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
输入：grid=[[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径1→3→1→1→1的总和最小。
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
f[i][j] = grid[i][j];
} else {
int top = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
f[i][j] = Math.min(top, left);
}
}
}
return f[m - 1][n - 1];
}对于每一块方块来说，只能从他的上边或者左边走过来，所以在for循环中的要取上边过来的和左边过来的最小的。文章来源：https://www.toymoban.com/news/detail-696722.html
并且在dp中的二维数组中每一个位置存放的都是到当前位置的最小路径和。文章来源地址https://www.toymoban.com/news/detail-696722.html
到了这里，关于算法通关村第十九关——最小路径和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
