【动态规划】LeetCode-64.最小路径和

🎈算法那些事专栏说明：这是一个记录刷题日常的专栏，每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目，在这立下Flag🚩
🏠个人主页：Jammingpro
📕专栏链接：算法那些事
🎯每日学习一点点，技术累计看得见

题目

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

执行示例

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

题解

由题目可知，我们只能向下走或者向右走。反过来说，到达第i行第j列，其上一步是第i-1行第j列项下走1步，或者是第i行第j-1列向右走1步。例如：第0行第0列元素可以向下走到第1行第0列，或者向右走1步到第0行第1列，如下图左图所示。例如：第1行第1列元素可以从第0行第1列元素向下走1步到达，可以是从第1行第0列向右走1步到达。

在这里插入图片描述
题目要求到达右下角的最小路径和，我们可以使用一个dp表（二维数组）来保存到达第i行第j列的最小路径和。由于我们只能向下或向右走，所以第0行元素初始化规则为：dp[0][0]=grid[0][0]，余下元素为dp[0][i]=dp[0][i-1]+grid[0][i]。同理，第0列元素初始化规则为：dp[0][0]=grid[0][0]，余下元素为dp[i][0]=dp[i-1][0]+grid[i][0]。示例1的第0行和第0列初始化示意图如下↓↓↓
在这里插入图片描述
而余下的元素的最小路径求解公式为dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j]。也就是说，到达当前位置可以从上一行同列元素向下走1步到达，也可以从上一列同一行元素向右走1步到达，选择从上到下还是从左到右，取决于哪个的最小路径和更小。下图演示示例1的执行过程↓↓↓
在这里插入图片描述
经过上面的分析，我们可以得到如下代码↓↓↓

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        //初始化第0行
        for(int i = 1; i < n; i++)
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        //初始化第0列
        for(int i = 1; i < m; i++)
            dp[i][0] = dp[i - 1][0] + grid[i][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][j];
        return dp[m - 1][n - 1];
    }
};

上面的代码中，我们专门使用两处循环用于初始化第0行和第0列。我们可以通过对dp表增开1行1列，并将增开的1行1列的dp[0][1]和dp[1][0]初始化为0，余下元素初始化INT_MAX，即可省去上述初始化过程。构建的dp表如下图所示，其中※所在位置，对应上个代码的dp表。
ps：为什么要这么初始化呢？因为从我们总结出的公式dp[j][j]=min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1]可以看到，求解dp[0][0]时，min(dp[i-1][j], dp[i][j-1])为0，则不会影响其结果；求解余下第0行和第0列的元素时，由于min(dp[i-1][j], dp[i][j-1])，则一定不会选择INT_MAX，而会选择第0行的前1列元素或第0列的前1行元素。
在这里插入图片描述
上述思路实现的代码如下，代码行数确实有所减少↓↓↓

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 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];
    }
};