LeetCode题：931下降路径最小和

骑猪看日落 2024-02-05 12:40 35阅读 0赞

**目录**

一、题目要求

二、解题思路

（1）状态表示

（2）状态转移方程

（3）初始化

（4）填表顺序

（5）返回值

三、代码

--------------------

## 一、题目要求 ##

[931. 下降路径最小和][931.]

> 给你一个 `n x n` 的 **方形** 整数数组 `matrix` ，请你找出并返回通过 `matrix` 的**下降路径**的**最小和** 。
> 
> **下降路径** 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 `(row, col)` 的下一个元素应当是 `(row + 1, col - 1)`、`(row + 1, col)` 或者 `(row + 1, col + 1)` 。
> 
> **示例 1：**
> 
> ![05e8399afb687beb5f7ac70a7704f789.jpeg][]
> 
>     输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
>     输出：13
>     解释：如图所示，为和最小的两条下降路径
> 
> **示例 2：**
> 
> ![936c8ad1e9da76ca5ddd54c92b08b8db.jpeg][]
> 
>     输入：matrix = [[-19,57],[-40,-5]]
>     输出：-59
>     解释：如图所示，为和最小的下降路径
> 
> **提示：**
> 
>  *  `n == matrix.length == matrix[i].length`
>  *  `1 <= n <= 100`
>  *  `-100 <= matrix[i][j] <= 100`

--------------------

## 二、解题思路 ##

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

### （1）状态表示 ###

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

### （2）状态转移方程 ###

如图：

![50082156a1494df9ac95448991527959.png][]

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

![92bad7ad9d774230bd5894607be60d38.png][]

### （3）初始化 ###

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

![e77f120d69484412b792c4269ceb3094.png][]

### （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;
        }
    }

[931.]: https://leetcode.cn/problems/minimum-falling-path-sum/
[05e8399afb687beb5f7ac70a7704f789.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/54f9a4b988dd4fbaa690452d55664b58.png
[936c8ad1e9da76ca5ddd54c92b08b8db.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/4ead6bef6d4f46e9b30d53704ee43892.png
[50082156a1494df9ac95448991527959.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/3078c99a24234e5f9efd310d71d0666c.png
[92bad7ad9d774230bd5894607be60d38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/a7cc2c9d47124312afb3e3d3fab4e904.png
[e77f120d69484412b792c4269ceb3094.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/a44e8ad58aff414f83c28888dfc4c669.png