1. 题目
64. 最小路径和
2. 描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
3. 实现方法
3.1 方法 1
3.1.1 思路
动态规划，分三步：
- 要从左上角走到右下角，我们定义
dp[i][j]为机器人走到(i, j)位置时最小的路径和，所以我们要的最终结果为dp[m - 1][n - 1]，其中m为行数，n为列数； - 要走到
(i, j)，我们有两种方式：- 从
(i - 1, j)走一步； - 从
(i, j - 1)走一步；
而要保证最终结果最小，我们就可以取两者中的最小值加上当前网格值就是最终结果
dp[i][j] = grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) - 从
- 接着考虑边界初始值，毫无疑问起点要赋值，即
dp[0][0] = grid[i][j]，然后就是在最上行和最左列：- 最上行，只能一直往左走，
dp[0][j] = dp[0][j - 1] grid[0][j] - 最左列，只能一直往上走，
dp[i][0] = dp[i - 1][0] grid[i][0]
- 最上行，只能一直往左走，
3.1.2 实现
代码语言：javascript复制public int minPathSum(int[][] grid) {
// dp
int m = grid.length;
int n = grid[0].length;
if(m <= 0 || n <= 0){
return 0;
}
// 声明
int[][] dp = new int[m][n];
// 起点
dp[0][0] = grid[0][0];
// 最上行
for(int i = 1; i < n; i ){
dp[0][i] = dp[0][i - 1] grid[0][i];
}
// 最左列
for(int i = 1; i < m; i ){
dp[i][0] = dp[i - 1][0] grid[i][0];
}
// 求最小路径
for(int i = 1; i < m; i ){
for(int j = 1; j < n; j ){
dp[i][j] = grid[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
