05 August 2008
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
1
2
3
4
5
6
7
8
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
给一个二维数组，从左上到右下找一条经过的元素加起来最小的path，返回所有元素加起来的和。全局最优，用DP， dp[i][j] = grid[i][j] + min(dp[i - 1][j])，所有路径经过的元素之和等于当前元素的值加上上一个可到达的元素的总和最小值。
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
26
27
class Solution {
// dp[i][j], i,j位置上最短路径的和
// dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];//初始化第一个值
//初始化第一行和第一列
for (int i = 1; i < m; i++) {//第一行，上一步的最小值 + 当前值
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {//第一列，上一步的最小值 + 当前值
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; //上一步的最小值 + 当前值
}
}
return dp[m - 1][n - 1];
}
}
滚动行或者滚动列，空间复杂度由O(m * n)变为O(n)或O(m)
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
26
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int[] dp = new int[n]; // 滚动行
dp[0] = grid[0][0];
for (int j = 1; j < n; j++) {//初始化第一行
dp[j] = dp[j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
dp[j] += grid[i][j]; // 直接从上面加过来
} else {
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]; //比较上面和左边
}
}
}
return dp[n - 1];
}
}
直接在原数组上修改，空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
// 先修改第一行和第一列，也可以放在最后的循环里面，不过有很多if...else
for (int i = 1; i < m; i++) {//初始化第一列
grid[i][0] = grid[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {//初始化第一行
grid[0][j] = grid[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
return grid[m - 1][n - 1];
}
}