931. 下降路径最小和

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

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

状态转移：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j + 1]) + matrix[i][j]

状态初始化：dp 的第一行 等于 arr的第一行

时间复杂度：O(m * n)

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

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        //初始化dp
        for(int i = 1; i < m; i++){
            for(int j = 0; j < n ; j++){
                int left = j - 1 >= 0 ? matrix[i - 1][j - 1] : Integer.MAX_VALUE;
                int top = matrix[i - 1][j];
                int right = j + 1 < n ? matrix[i - 1][j + 1] : Integer.MAX_VALUE;
                matrix[i][j] = Math.min(left, Math.min(top, right)) + matrix[i][j];
            }
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            ans = Math.min(ans, matrix[m - 1][i]);
        }
        return ans;
    }
}