目录
一、题目要求
给你一个
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].length1 <= 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;
}
}
