原题
给定一个包含非负整数的 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/