HHot 100C++ 图解

64. 最小路径和

中等 多维动态规划 3 帧动画 在力扣上做

一句话套路格值 + 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.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

思路

时间O(mn)
空间O(n)

状态

dp[i][j] = 到 (i,j) 的最小路径和 = grid[i][j] + min(上, 左)。

边界

第一行只能从左来,第一列只能从上来 —— 忘记这两行初始化是新手最常见错误。

技巧

可以直接在 grid 上原地改(LeetCode 允许,本地练习时注意它改的是入参)。

变体

Q174 地下城游戏(要从右下角反向 DP,因为「血量」不能为 0,正着推不满足最优子结构 —— 很好的「为什么方向要反」例子);三角形最小路径和 Q120。

图解

j0 j1 j2 i0 1 3 1 i1 1 5 1 i2 4 2 1
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/16_dp_multidim.cpp22 行
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];
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q64_minimum_path_sum11 行
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);

↑↓ 选择↵ 打开/ 随时唤起