给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
1
2
3
4
5
6
7
8
| 输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
|
我们创建二维 dp 数组，dp[i][j]表示从左上角出发到(i, j)位置的最小路径和。dp[0][0]=grid[0][0]。对于其他元素有以下方程：
- 当 i = 0，j > 0 时，
dp[0][j] = dp[0][j - 1] + grid[0][j]；
- 当 j = 0，i > 0 时，
dp[i][0] = dp[i - 1][0] + grid[i][0]；
- 当 j > 0，i > 0 时，
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])。
dp[m - 1][n - 1]即为从左上角到右下角的路径和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
int[][] cost = new int[row][col];
cost[0][0] = grid[0][0];
for(int i=1; i<row; ++i){
cost[i][0] = cost[i-1][0] + grid[i][0];
}
for(int i=1; i<col; ++i){
cost[0][i] = cost[0][i-1] + grid[0][i];
}
for(int i=1; i<row; i++){
for(int j=1; j<col; j++){
cost[i][j] = Math.min(cost[i-1][j],cost[i][j-1])+grid[i][j];
}
}
return cost[row-1][col-1];
}
}
|
时间复杂度O(mn)，空间复杂度O(mn)。
我们可以使用滚动数组来优化空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
int[] cost = new int[col];
cost[0] = grid[0][0];
for(int i=1; i<col; ++i){
cost[i] = cost[i-1] + grid[0][i];
}
for(int i=1; i<row; i++){
for(int j=0; j<col; j++){
int left = j > 0 ? cost[j - 1] : Integer.MAX_VALUE;
cost[j] = Math.min(cost[j],left)+grid[i][j];
}
}
return cost[col-1];
}
}
|
时间复杂度O(mn)，空间复杂度O(n)。