最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
1
2
3
| 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
|
思路1: 递归，当前位置到结束的最小路径和等于往左往右走较小和加上当前路径值即可
代码（思路1）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
int width = 0;
int height = 0;
public int minPathSum(int[][] grid) {
width = grid[0].length;
height = grid.length;
return minPath(grid, 0, 0);
}
public int minPath(int[][] grid, int row, int column) {
if(row == height || column == width) {
return Integer.MAX_VALUE;
}
if(row == height-1 && column == width-1){
return grid[row][column];
}
int right = minPath(grid, row+1, column);
int down = minPath(grid, row, column + 1);
return Math.min(right, down) + grid[row][column];
}
}
|
思路2: 思路1在leetcode中超时，所以通过dp来做，可以维护dp数组表示当前节点到结束的最短路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int minPathSum(int[][] grid) {
int width = grid[0].length;
int height = grid.length;
int[][] dp = new int[height][width];
for(int row = height - 1; row >= 0; row--) {
for(int column = width - 1; column >= 0; column--) {
if(row == height - 1 && column == width - 1) {
dp[row][column] = grid[row][column];
}else{
int min = Integer.MAX_VALUE;
if(column < width - 1){
min = dp[row][column+1];
}
if(row < height - 1){
min = Math.min(min, dp[row+1][column]);
}
dp[row][column] = min + grid[row][column];
}
}
}
return dp[0][0];
}
}
|