931. 下降路径最小和(Java、动态规划、备忘录)

首先从底向上分析原型
dp二维数组记录的是每一层下降的路径和
对于matrix[i][j]，只有可能从matrix[i-1][j],matrix[i-1][j-1],matrix[i-1][j+1] 这三个位置转移过来
然后用备忘录的方法消除重叠子问题，防止重复计算，如果存结果了，就直接返回；没存，就去递归计算

class Solution {
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int res = Integer.MAX_VALUE;
        memo = new int[n][n];
        for(int i = 0;i
            Arrays.fill(memo[i],666666);
        }
        for(int j = 0;j
            res = Math.min(res,dp(matrix,n-1,j));
        }

        return res;
    }
    int dp(int[][]matrix,int i,int j){
        if(i<0||j<0||i>=matrix.length||j>=matrix.length){
            return Integer.MAX_VALUE;
        }
        if(i == 0){
            return matrix[i][j];
        }

        if(memo[i][j] != 666666){
            return memo[i][j];
        }

        memo[i][j] = matrix[i][j] + min(
            dp(matrix,i-1,j),
            dp(matrix,i-1,j+1),
            dp(matrix,i-1,j-1)
        );
        return memo[i][j];
    }

    int min(int a,int b,int c){
        return Math.min(a,Math.min(b,c));
    }
}