小旭讲解 LeetCode 64. 最小路径和

原题

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

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

示例:

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

思路

这道题目可以发现点 $(r, c)$ 的最小路径由左侧点 $(r, c - 1)$ 和上面的点 $(r - 1, c)$ 来决定，即：

sum(r, c) = min(sum(r, c - 1), sum(r + 1, c)) + grid(r, c)

故，每一个点我们都需要保留其最优值 —— 从起点到当前点的最小路径和，即所谓的最优子结构性质；同时，每一个点的最优值是由另外两个规模更小的点决定的，即所谓的重叠子问题性质。

那么，我们可以使用动态规划的方式来解。

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int r = grid.size(), c = grid[0].size();
        vector<vector<int>> dp(r, vector<int>(c, INT_MAX));
        dp[0][0] = grid[0][0];
        vector<int> d{0, -1, 0};
        for (int cr = 0; cr < r; ++cr) {
            for (int cc = 0; cc < c; ++cc) {
                for (int di = 0; di < 2; ++di) {
                    int nr = cr + d[di];
                    int nc = cc + d[di + 1];
                    if (nr < 0 || nc < 0) continue;
                    dp[cr][cc] = min(dp[cr][cc], dp[nr][nc] + grid[cr][cc]);
                }
            }
        }
        return dp[r - 1][c - 1];
    }
};

复杂度分析

时间复杂度： $O(R * C)$ R 代表行数，C代表列数
空间复杂度： $O(R * C)$

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/minimum-path-sum/.

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-64-minimum-path-sum/