1、题目
931. 下降路径最小和
2、题解
定义一个保存状态的二维数组,第一行初始化为A[0],接着剩下行满足状态方程:
dp[i][j] =A[i][j] + min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]);分三种情况,当为第一列时,当为最后一列时,当为中间列时。最后取状态数组最后一行中的最小值。
3、代码
//931
class Solution {
public int minFallingPathSum(int[][] A) {
if (A.length == 0 || A[0].length == 0) {
return 0;
}
int[][] res = new int[A.length][A[0].length];
for(int i = 0; i < A[0].length; i++) {
res[0][i] = A[0][i];
}
for (int i = 1; i < A.length; i++) {
for (int j = 0; j < A[i].length; j++) {
if (j == 0) {
res[i][j] = Math.min(res[i - 1][j + 1], res[i - 1][j]) + A[i][j];
} else if (j == A[i].length - 1) {
res[i][j] = Math.min(res[i - 1][j - 1], res[i - 1][j]) + A[i][j];
} else {
res[i][j] = Math.min(Math.min(res[i - 1][j + 1], res[i - 1][j - 1]), res[i - 1][j]) + A[i][j];
}
}
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < res[res.length - 1].length; i++) {
if(res[res.length - 1][i] < min) {
min = res[res.length - 1][i];
}
}
return min;
}
}
网友评论