美文网首页
LeetCode 931. 下降路径最小和

LeetCode 931. 下降路径最小和

作者: 风卷晨沙 | 来源:发表于2019-09-18 11:22 被阅读0次

    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;
            }
    
        }
    

    4、执行结果

    image.png

    相关文章

      网友评论

          本文标题:LeetCode 931. 下降路径最小和

          本文链接:https://www.haomeiwen.com/subject/ocucyctx.html