LeetCode 931：下降路径最小和

链接

思路：

子结构：
对于 matrix[i][j]，只有可能从 matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1] 这三 个位置转移过来。

那么，只要知道到达 (i-1, j), (i-1, j-1), (i-1, j+1) 上一层三个可能传入的元素的 最小路径和， + matrix[i][j] 元素的值，就能够计算出来到达位置 (i, j) 的最⼩路径和；

思路：

1. dp函数的定义：从第⼀⾏（matrix[0][j]）向下落，落到位置 matrix [i][j] 的最小路径和为 dp(matrix, i, j)。
2. dp的参数matrix[i][j] 元素即为状态；
3. 到matrix[i][j]的最小和结果分解为上一层 (i-1, j), (i-1, j-1), (i-1, j+1) 三个子结构，子问题互相独立；
4. 重叠子问题： matrix[i][j]会被反复用到，如算（i,j）需要 (i-1, j), (i-1,j-1), (i-1,j+1) ，而算（i,j+1）需要 (i-1,j+1),(i-1,j), (i-1,j+2)， 就有 (i-1,j), (i-1,j+1) 被重复计算 ！

暴力递归解：

class Solution {
    
    public int minFallingPathSum(int[][] matrix) {
    
        int n =matrix.length;
        int res=Integer.MAX_VALUE;

        // 遍历最后一行的所有列, dp函数返回第j列的最小路径和
        for(int j=0;j<n;j++){
    
            res=Math.min(res,dp(matrix,n-1,j)); // 传入dp的状态参数为最后一行的每个元素，算出最小的结果即为所求
        }
        return res;
    }


    int  dp(int[][] matrix,int i,int j){
    	
		// base case
        // 二维数组越界返回最大值，取不到
        if(i<0 ||j<0 || 
        i>=matrix.length || 
        j>=matrix[0].length){
       
            return Integer.MAX_VALUE;
        }

        if(i==0){
     // 只有一行
            return matrix[0][j];
        }

        // 状态转移方程，返回到当前行第 j 列的最小路径和
        // 结果 = 依次递归求出每个状态参数的最小路径和 + 当前节点元素值
        int sub=matrix[i][j]+min(dp(matrix,i-1,j),dp(matrix,i-1,j-1),dp(matrix,i-1,j+1));
        return sub;
    }
    

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

想象递归树的第一层节点就是 二维数组的最后一行，但树的第一层有n个节点而不是一个根节点，所以需要在main中依次遍历数组最后一行的 每个元素；
二维数组每往上一层，就是树的节点向下递归走一次，
在到达第一层后（递归到i=0树的底部）由base case返回 matrix [0][j] ，再将每一层min的结果依次回溯传给最后一行的 matrix [n-1][j]即树的第一层

使用递归+备忘录：

class Solution {
    
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
    
        int n =matrix.length;
        int res=Integer.MAX_VALUE;
        // dp数组意为从第一行到 matrix[i][j]的最小和
        memo=new int[n][n]; 
        for(int i=0;i<n;i++){
     // 由于求的是最小，需要将memo初始化为取不到的大
            Arrays.fill(memo[i],Integer.MAX_VALUE); // 初始化每行的每个元素
        }
        for(int j=0;j<n;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[0].length){
       
            return Integer.MAX_VALUE;
        }
        // base case
        if(i==0){
     // 只有一行
            return matrix[0][j];
        }
        // 重叠子问题
        if(memo[i][j]!=Integer.MAX_VALUE){
    
            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));
    }
}

补充：
比如要求我们的算法复杂度是 O(NlogN)，你想想怎么才能搞出⼀个对数级别的复杂度呢？ 肯定得⽤到 ⼆分搜索 或者⼆叉树相关的数据结构，⽐如 TreeMap，PriorityQueue 之类的对吧。 再⽐如，有时候题⽬要求你的算法时间复杂度是 O(MN)，这可以联想到什么？ 可以⼤胆猜测，常规解法是⽤ 回溯算法 暴⼒穷举，但是更好的解法是动态规划，⽽且是⼀个⼆维动态规划， 需要⼀个 M * N 的⼆维 dp 数组，所以产⽣了这样⼀个时间复杂度。