【学会动态规划】最小路径和（9）

动态规划怎么学？

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

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

1. 题目解析

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

这道题目不难理解，就是从右上角开始，

只能往右或者往下走，计算走到右下角的最小路径和即可。

2. 算法原理

1. 状态表示

dp[ i ][ j ] 就表示从起点到 [ i，j ] 位置的最小路径和。

2. 状态转移方程

根据最近的一步划分问题，而到 [ i，j ] 位置有两种情况，

一个是从上面来：dp[ i - 1 ][ j ] + g[ i ][ j ]

一个是从左边来：dp[ i ][ j - 1 ] + g[ i ][ j ]

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

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

3. 初始化

初始化是为了防止越界，所以我们只需要多加上面一行和左边一行即可,

不过里面填的值要保证不影响后面的填表，所以我们可以将整个表初始化成正无穷大，

然后为了让第一次填表不出问题，就把第一个位置上面的位置初始化成0即可。

4. 填表顺序

从上往下，从左往右

5. 返回值

返回右下角的最小路径和即可。

3. 代码编写

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~