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
| class Solution {
private Integer[][] memo;
public int minFallingPathSum(int[][] matrix) {
memo = new Integer[matrix.length][matrix[0].length];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < matrix[0].length; i++) {
ans = Math.min(ans, backtrack(matrix, 0, i));
}
return ans;
}
private int backtrack(int[][] matrix, int row, int col) {
if (memo[row][col] != null) {
return memo[row][col];
}
if (row == matrix.length - 1) {
return matrix[row][col];
}
int ans = matrix[row][col], minSubPath = Integer.MAX_VALUE;
for (int i = -1; i <= 1; i++) {
int newRow = row + 1, newCol = col + i;
if (!isOutOfBound(matrix, newRow, newCol)) {
minSubPath = Math.min(minSubPath, backtrack(matrix, newRow, newCol));
}
}
return memo[row][col] = ans + minSubPath;
}
private boolean isOutOfBound(int[][] matrix, int row, int col) {
return row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length;
}
}
|
