【动态规划】08路径问题_下降路径最小和_C++（medium）

题目链接：leetcode下降路径最小和

---

目录

题目解析：

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码

---

题目解析：

题目让我们求通过?matrix?的下降路径?的?最小和?

由题可得：

在下一行选择的元素和当前行所选元素最多相隔一列

（即位于正下方或者沿对角线向左或者向右的第一个元素）

如图：

我们用示例一分析：

当我们从数字1开始走的时，此时有如上图几种走法；

其他数字也是同理

我们这里只要下降路径?的?最小和，

所以这里我们这里可以得到这两条下降路径和最短：

---

算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义（是什么？）

dp[i][j]表示到达[i][j]位置的下降路径的最小和。

这种状态表示怎么来的？

1.经验+题目要求

用之前或者之后的状态，推导出dp[i][j]的值；

根据最近的最近的一步，来划分问题

经验：以[i][j]位置为结尾，用之前的状态推导出dp[i][j]的值

题目要求：求下降路径?的?最小和

2.状态转移方程

dp[i][j]等于什么？

根据最近的最近的一步，来划分问题

如图，求[i][j]位置的下降路径的最小和时，分为三种情况：

第一种：从[i-1][j-1]位置加上[i][j]位置的值

我们此时只要用到达[i-1][j-1]位置的下降路径的最小和，再加上[i][j]位置的值（matrix[i][j]）就可以得到下降路径的最小和。

而这里的“到达[i-1][j-1]位置的下降路径的最小和”正好是我们的状态表示dp[i-1][j-1];

即：dp[i]=dp[i-1][j-1]+matrix[i][j]

第二种：从[i-1][j]位置加上[i][j]位置的值

我们此时只要用到达[i-1][j]位置的下降路径的最小和，再加上[i][j]位置的值（matrix[i][j]）就可以得到下降路径的最小和。

而这里的“到达[i-1][j]位置的下降路径的最小和”正好是我们的状态表示dp[i-1][j];

即：dp[i]=dp[i-1][j]+matrix[i][j]

第三种：从[i-1][j+1]位置加上[i][j]位置的值

我们此时只要用到达[i-1][j+1]位置的下降路径的最小和，再加上[i][j]位置的值（matrix[i][j]）就可以得到下降路径的最小和。

而这里的“到达[i-1][j+1]位置的下降路径的最小和”正好是我们的状态表示dp[i-1][j+1];

即：dp[i]=dp[i-1][j+1]+matrix[i][j]

总结以上三种情况：

因为我们这里要取下降路径的最小和

所以状态转移方程应该为：

dp[i][j]=min({(int)dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]})+matrix[i-1][j-1];

3.初始化

(保证填表的时候不越界)

在0行0列和n列的时候越界，所以我们这里可以在m*n的外围多加1行2列，如图：

还有一个问题是：

我们要拿新增用来初始化的行和列要初始化为几呢？

这里我们需要注意的一点就是在dp[1][1]的时候，最小的下降路径就是他本身

根据状态转移方程，如下图三个位置会影响他的值

为了能够取到他本身，

我们这里需要把这三个位置的其中一个初始化为0，其他的位置初始化为INT_MAX（无穷大）

4.填表顺序

（为了填写当前状态的时候，所需要的状态已经计算过了）

这里所需要的状态是：dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]

所以应该从上到下，从左到右填表

5.返回值

（根据题目要求和状态表示）

综上分析：

返回值为：最后一行的最小值

---

编写代码:

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
    //1.创建dp表
    //2.初始化
    //3.填表
    //4.返回结果

        int n=matrix.size();
        vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
        for(int i=0;i<n+2;i++)
            dp[0][i]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=min({(int)dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]})+matrix[i-1][j-1];

        int tmp=INT_MAX;
        for(int i=0;i<=n;i++)
        {
            tmp=min(tmp,dp[n][i]);
        }

        return tmp;    
    }
};