image.png

    状态定义：dp[i][j] 表示到达 （i，j）处的最小数字和

    问题目标：max(dp数组的最后一行的元素)

    状态转移：dp[i][j] = min(dp[i-1][0], dp[i-1][j-1], dp[i-1][j + 1], dp[i-1][n-1]) + arr[i][j]，除了第 i - 1 行的 第 j 列不可取，第 i - 1 行其他列的状态都可以转移到当前状态

    状态初始化：dp 的第一行 等于 arr的第一行，dp其他的元素初始化为无穷大

    时间复杂度：O(n n n) ——可优化为 O(n * n)

    空间复杂度：O(n * n) ——可优化

    1. class Solution {
    2.     public int minFallingPathSum(int[][] grid) {
    3.         int m = grid.length;
    4.         int n = grid[0].length;
    5.         int[][] dp = new int[m][n];
    7.         for(int i = 0; i < n; i++){
    8.             dp[0][i] = grid[0][i];
    9.         }
    10.         for(int i = 1; i < m; i++){
    11.             for(int j = 0; j < n; j++){
    12.                 dp[i][j] = Integer.MAX_VALUE; //需要初始化为无穷大
    14.                 for(int k = 0; k < n; k++){ //上一行同一列的状态不能转移到当前状态
    15.                     if(j != k){
    16.                         dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + grid[i][j]);
    17.                     }
    18.                 }
    19.             }
    20.         }
    21.         int ans = Integer.MAX_VALUE;
    22.         for(int i = 0; i < n; i++){
    23.             ans = Math.min(ans, dp[m-1][i]);
    24.         }
    26.         return ans;
    27.     }
    28. }