【学会动态规划】下降路径最小和（8）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】下降路径最小和（8）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：931. 下降路径最小和 - 力扣（Leetcode）

【学会动态规划】下降路径最小和（8）,学会动态规划,动态规划,算法,leetcode

这道题读着非常拗口，但是画个图可以很好的理解：

比如说我们从箭头指向的这一格开始：

【学会动态规划】下降路径最小和（8）,学会动态规划,动态规划,算法,leetcode

他能往下走的路径就i是图中的三个格子。

找出路径的最小和然后返回即可。

2. 算法原理

1. 状态表示

dp[ i ][ j ] 表示什么呢？

dp[ i ][ j ] 表示到达[ i，j ]的时候的路径最小值。

2. 状态转移方程

从最近的一步来找，而最近的一步有三种情况：

1. 从左上方来：dp[ i - 1 ][ j - 1 ] + m[ i ][ j ]

2. 从正上方来：dp[ i - 1 ][ j ] + m[ i ][ j ]

3. 从右上方来：dp[ i - 1 ][ j + 1 ] + m[ i ][ j ]

因为我们要的是最小的路径和，所以状态转移方程就是：

dp[ i ][ j ] = min( dp[ i - 1 ][ j - 1 ]，dp[ i - 1 ][ j ]，dp[ i - 1 ][ j + 1 ] ) + m[ i ][ j ]

3. 初始化

为了防止越界，我们得在最左边最上面最右边都加一行。

但是左边和右边的那两行可不能初始化成0，得初始化成很大的数防止对计算产生影响。

所以我们就先把所有位置都变成很大的数，然后把第一行改成0就行。

4. 填表顺序

从上往下，从左往右（这个是无所谓的（因为左右的值是用不上的））

5. 返回值

返回最后一行的最小值。

3. 代码编写

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size(); 
        vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));
        for(auto& e : dp[0]) e = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))
                + matrix[i - 1][j - 1];
            }
        }
        int ans = INT_MAX;
        for(const auto& k : dp[m]) ans = min(ans, k);
        return ans; 
    }
};