LeetCode 931. 下降路径最小和

1、题目

image.png

2、分析

方法一：递归
主要就是找出dp函数。
这个 dp 函数的含义：
从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)
dp函数的实现：

image.png

方法二：动态规划
我们用 dp(i, j) 表示从位置为 (i, j) 的元素开始的下降路径最小和。根据题目的要求，位置 (i, j) 可以下降到 (i + 1, j - 1)，(i + 1, j) 和 (i + 1, j + 1) 三个位置（先不考虑超出数组边界的情况），因此状态转移方程为：
dp(i, j) = A[i][j] + min{dp(i + 1, j - 1), dp(i + 1, j), dp(i + 1, j + 1)}

3、代码

方法一代码：

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

   private int dp(int[][] matrix, int i, int j){
       int m = matrix.length;
       int n = matrix[0].length;
       if(i < 0 || j < 0 || j >= n){
           return Integer.MAX_VALUE;
       }
       if(i == 0) return matrix[i][j];
       if(memo[i][j] != Integer.MAX_VALUE) return memo[i][j];
       //这个节点的最小和，等于上面三个节点的最小和 加上 本节点
       memo[i][j] = matrix[i][j] + Math.min(dp(matrix, i - 1, j - 1), Math.min(dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1)));
       return memo[i][j];
   }
}

方法二代码：

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int N = matrix.length;
        for(int i = N - 2; i >= 0; i--){
            for(int j = 0; j < N; j++){
                if(j == 0){
                    //第一列
                    matrix[i][j] += Math.min(matrix[i + 1][j], matrix[i + 1][j + 1]);
                }else if(j + 1 == N){
                    //最后一列
                    matrix[i][j] += Math.min(matrix[i + 1][j - 1], matrix[i + 1][j]);
                }else{
                    //中间列
                    matrix[i][j] += Math.min(Math.min(matrix[i + 1][j - 1], matrix[i + 1][j]), matrix[i + 1][j + 1]);
                }
            }
        }
        //最小和都在第一列中，比较即可获得最终答案
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++){
            res = Math.min(res, matrix[0][i]);
        }
        return res;
    }
}