64. 最小路径和
一句话套路格值 + min(上,左),首行首列单独初始化
题目描述
给定一个包含非负整数的 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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
思路
时间
O(mn)空间
O(n)状态
dp[i][j] = 到 (i,j) 的最小路径和 = grid[i][j] + min(上, 左)。
边界
第一行只能从左来,第一列只能从上来 —— 忘记这两行初始化是新手最常见错误。
技巧
可以直接在 grid 上原地改(LeetCode 允许,本地练习时注意它改的是入参)。
变体
Q174 地下城游戏(要从右下角反向 DP,因为「血量」不能为 0,正着推不满足最优子结构 —— 很好的「为什么方向要反」例子);三角形最小路径和 Q120。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0064 {
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0; // 防 grid[0].size() 越界
const int R = (int)grid.size(), C = (int)grid[0].size();
vector<int> dp(C);
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j) {
if (i == 0 && j == 0)
dp[j] = grid[0][0];
else if (i == 0)
dp[j] = dp[j - 1] + grid[i][j]; // 第一行:只有左边
else if (j == 0)
dp[j] = dp[j] + grid[i][j]; // 第一列:dp[j] 旧值即上一行
else
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
}
return dp[C - 1];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0064::Solution s;
vector<vector<int>> a{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
CHECK_EQ(s.minPathSum(a), 7); // 1->3->1->1->1
vector<vector<int>> b{{1, 2, 3}, {4, 5, 6}};
CHECK_EQ(s.minPathSum(b), 12);
vector<vector<int>> c{{5}};
CHECK_EQ(s.minPathSum(c), 5);
vector<vector<int>> d{{1, 2, 3}}; // 单行
CHECK_EQ(s.minPathSum(d), 6);
vector<vector<int>> e{{1}, {2}, {3}}; // 单列
CHECK_EQ(s.minPathSum(e), 6);