05 August 2008
n x n 矩阵中，从上到下的一条路径，路径和最小
二维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
26
27
28
29
30
31
32
33
34
class Solution {
// dp[i][j]存储原数组i,j位置处能累加的最小下降和
// dp[i][j] = matrix[i][j] + Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]),dp[i - 1][j + 1])
public int minFallingPathSum(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int len = matrix.length; // 是 n X n 的矩阵
if (len == 1) { // 1 x 1的矩阵
return matrix[0][0];
}
int[][] dp = new int[len][len];
for (int j = 0; j < len; j++) { //第一行的各个值为初始化的值
dp[0][j] = matrix[0][j];
}
for (int i = 1; i < len; i++) {
for (int j = 0; j < len; j++) {
if (j == 0) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
} else if (j == len - 1) {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i][j];
}
}
}
// 遍历最后一行，找到最小值
return Arrays.stream(dp[len - 1]).min().getAsInt();
}
}
上面的做法空间复杂度是O(n * n)，如果额外用一个一维的滚动数组，空间复杂度为O(n)；如果直接在原数组上修改，空间复杂度为O(1)
修改原数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minFallingPathSum(int[][] matrix) {
int len = matrix.length;
for(int i = 1; i < len; i++){
for(int j = 0; j < len; j++){
int oneRowMin;
if(j == 0) {
oneRowMin = Math.min(matrix[i-1][j], matrix[i - 1][j + 1]);
} else if (j == len - 1){
oneRowMin = Math.min(matrix[i-1][j], matrix[i - 1][j - 1]);
} else {
oneRowMin = Math.min(Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]), matrix[i - 1][j + 1]);
}
matrix[i][j] += oneRowMin;
}
}
return Arrays.stream(matrix[len - 1]).min().getAsInt();
}
}