本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
1、题目
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
2、解题
经典的动态规划题
- 每次只能向下或者向右
- 那么dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; 只要组装第一行和第一列然后双重循环就可以
- 最后返回右下角的数据dp[row-1][column-1];
public static int minPathSum(int[][] grid) {
if (null == grid || 0 == grid.length || 0 == grid[0].length) {
return 0;
}
int row = grid.length;
int column = grid[0].length;
int[][] dp = new int[row][column];
dp[0][0] = grid[0][0];
//组装第一列
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
//组装第一行
for (int i = 1; i < column; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < column; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][column - 1];
}
