LeetCode题：931下降路径最小和

一、题目要求

931. 下降路径最小和

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]

输出：13

解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]

输出：-59

解释：如图所示，为和最小的下降路径

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

二、解题思路

这题我们用动态规划思想解决问题，下面是动态规划的一些定义梳理：

（1）状态表示

       这里找到状态表示是通过：经验 + 题目要求，我们定义dp表里的某一位置，就是从上到下，在到达这个位置时的最小路径和。

（2）状态转移方程

如图：

       假设到达这个位置时，求到这里用的最小路径和，那么就是左上，正上，右上间选一个最小值，加上四角星位置原表的路径值。而左上，正上，右上在dp表中放的都是到达他们位置的最小路径，这也是我们状态表示时的定义。如图：

（3）初始化

      这里，我们再原表基础上要多加1行、2列，其中，第一行可以放0，因为dp对应原表的i j 位置，加上0是不影响这个映射位置要放的值。但是第一列和最后一列就不能放0了，因为定义dp表的位置，都要从左上，正上，右上取出最小值，再加上原表在dp表上映射的位置；所以第一列和最后一列，我们放整型的最大值：Integer.MAX_VALUE。如图：

（4）填表顺序

      从上到下（因为要根据上面的值才能推出当前位置的值），为了方便，再从左到右

（5）返回值

       返回dp表最后一行的最小值

三、代码

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        //1、建立dp表
        int n = matrix.length;//方形的，不用分别求行和列了
        int[][] dp = new int[n + 1][n + 2];
        //2、初始化dp表
        for(int i = 1; i < n + 1; i++) {
            //dp的第一列和最后一列赋值整型的最大值
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }
        //3、填表
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                //左上，上，右上的最小值 + 此时原表的值
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        //4、返回值
        int min = dp[n][0];
        for(int i = 1; i < n + 1; i++) {
            //找出最后一行（第n行）的最小值，返回这个最小值
            min = Math.min(min, dp[n][i]);
        }
        return min;
    }
}