931. 下降路径最小和 (opens new window)

1.记忆化搜索+递归

思路参考：2746. 字符串连接删减字母 | Blage's Coding (blagecode.cn) (opens new window)

使用记忆化搜索进行剪枝。map保存以当前(x,y)位置作为起点的最小下降路径和。

class Solution {
    Map<String,Integer> map=new HashMap<>();
    public int minFallingPathSum(int[][] matrix) {
        int res=Integer.MAX_VALUE;
        for(int i=0;i<matrix[0].length;i++){
            res=Math.min(res,dfs(matrix,0,i));
        }
        return res;
    }
    public int dfs(int[][] matrix,int x,int y){
        String key=String.valueOf(x)+","+String.valueOf(y);
        if(map.containsKey(key)) return map.get(key);
        if(x==matrix.length-1){
            map.put(key,matrix[x][y]);
            return matrix[x][y];
        }
    
        int left=Integer.MAX_VALUE,mid=Integer.MAX_VALUE,right=Integer.MAX_VALUE;
        if(x+1<matrix.length&&y-1>=0){
            left=matrix[x][y]+dfs(matrix,x+1,y-1);
        }
        if(x+1<matrix.length){
            mid=matrix[x][y]+dfs(matrix,x+1,y);
        }
        if(x+1<matrix.length&&y+1<matrix[0].length){
            right=matrix[x][y]+dfs(matrix,x+1,y+1);
        }
        int min=Math.min(left,mid);
        min=Math.min(min,right);
        map.put(key,min);
        return min;
    }
}

2.动态规划

与上面思路相反，dp保存以当前位置作为终点的最小下降路径之和。

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int[][] dp=new int[matrix.length][matrix[0].length];
        int res=Integer.MAX_VALUE;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(i==0) dp[i][j]=matrix[i][j];
                else{
                    int upleft=j-1>=0?dp[i-1][j-1]:Integer.MAX_VALUE;
                    int upmid=dp[i-1][j];
                    int upright=j+1<matrix[0].length?dp[i-1][j+1]:Integer.MAX_VALUE;
                    int min=Math.min(upleft,upmid);
                    min=Math.min(min,upright);
                    dp[i][j]=matrix[i][j]+min;
                }
                if(i==matrix.length-1) res=Math.min(res,dp[i][j]);
            }
        }
        return res;
    }
}