欢迎光临
我们一直在努力

64. 最小路径和

64. 最小路径和

中等

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

📝 核心笔记:最小路径和 (Minimum Path Sum)

1. 核心思想 (一句话总结)

“比价游戏:想要到达当前格子 (i, j) 的花费最少,就得问问它的前一步——‘上面’和‘左面’哪个更便宜,选便宜的那个加上我自己的值。”

  • 状态定义:dfs(i, j) 表示从起点 (0, 0) 到达 (i, j) 的最小路径和。
  • 转移方程:dfs(i, j) = min(dfs(上), dfs(左)) + grid[i][j]。
  • 边界处理:越界的地方视为“无穷大代价”,这样 Math.min 永远不会选择越界的路。
2. 算法流程 (DFS + Memo)
  • 初始化 (Init):
      • memo 数组全填 -1。因为路径和肯定是非负的(题目提示数字非负),所以 -1 是安全的未计算标记。
      • 从终点 (m-1, n-1) 开始递归。
  • 递归 (Recursion):
      • 越界 (Out of Bound):如果 i < 0 或 j < 0,返回 Integer.MAX_VALUE。这是为了配合 Math.min,让这条路自然被淘汰。
      • 起点 (Base Case):如果到了 (0, 0),返回 grid[0][0]。
      • 查表 (Memo Lookup):如果 memo[i][j] != -1,直接返回。
  • 计算 (Calc):
      • 比较 dfs(上) 和 dfs(左),取小者。
      • 加上当前格子的值 grid[i][j]。
      • 存入 memo 并返回。
    🔍 代码回忆清单

    // 题目:LC 64. Minimum Path Sum
    class Solution {
    public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // memo[i][j] 记录到达 (i, j) 的最小路径和
    int[][] memo = new int[m][n];
    for (int[] row : memo) {
    Arrays.fill(row, -1); // -1 表示未计算
    }
    // 从终点倒着推
    return dfs(m – 1, n – 1, grid, memo);
    }

    private int dfs(int i, int j, int[][] grid, int[][] memo) {
    // 1. 越界检查 (撞墙)
    // 返回 MAX_VALUE 是为了让 Math.min 忽略这条路径
    // 注意:不能直接 return INT_MAX,防止外层 +grid[i][j] 溢出变成负数
    // 但题目 grid 值非负且路径不长,通常没事。严谨写法是返回一个"较大值"。
    if (i < 0 || j < 0) {
    return Integer.MAX_VALUE;
    }

    // 2. Base Case: 回到起点
    if (i == 0 && j == 0) {
    return grid[i][j];
    }

    // 3. 查表
    if (memo[i][j] != -1) {
    return memo[i][j];
    }

    // 4. 状态转移: min(来自左边, 来自上边) + 当前过路费
    return memo[i][j] = Math.min(
    dfs(i, j – 1, grid, memo),
    dfs(i – 1, j, grid, memo)
    ) + grid[i][j];
    }
    }

    ⚡ 快速复习 CheckList (易错点)
    • [ ] 为什么越界要返回 Integer.MAX_VALUE?
      • 如果返回 0,Math.min 就会误以为越界那边是“免费”的,导致路径一直往墙外跑。
      • 返回无穷大,才能在 min 比较中被剔除。
    • [ ] Integer.MAX_VALUE + grid[i][j] 会溢出吗?
      • 在 Java 中,MAX_VALUE + 正数 确实会溢出变成负数。
      • 隐患:如果测试用例真的让递归走到了墙外,且加上了当前的 grid 值,结果变成负数,Math.min 就会错误地选中它。
      • 修复:通常可以在越界时返回一个 Integer.MAX_VALUE / 2 或者在 Math.min 之前判断。不过 LeetCode 的数据通常不会触发这个问题(因为总有一条合法路径是有限值,min 会选中合法的那个)。
    • [ ] 递归方向?
      • 自顶向下(从终点问起点)。
      • 也可以写成 DP 迭代(从起点填到终点)。
    🖼️ 中文数字演练

    Grid = [[1, 3], [1, 5]] m=2, n=2. 终点 (1, 1),值是 5。

  • 启动 dfs(1, 1) (值5):
      • 需要 min(dfs(1, 0), dfs(0, 1)).
  • 分支 A: dfs(1, 0) (左下角, 值1):
      • 比较 dfs(1, -1) (左, 越界->INF) 和 dfs(0, 0) (上, 起点).
      • dfs(0, 0) 返回 1 (grid[0][0]).
      • min(INF, 1) + 1 = 2. 记录 memo[1][0] = 2.
  • 分支 B: dfs(0, 1) (右上角, 值3):
      • 比较 dfs(0, 0) (左, 起点) 和 dfs(-1, 1) (上, 越界->INF).
      • dfs(0, 0) 返回 1.
      • min(1, INF) + 3 = 4. 记录 memo[0][1] = 4.
  • 回到 dfs(1, 1):
      • min(2, 4) + 5 = 7.
  • 最终结果: 7.
  • 📝 核心笔记:最小路径和 (Minimum Path Sum – DP Iterative) 递推

    1. 核心思想 (一句话总结)

    “水流模型:把每个格子想象成从‘上方’或‘左方’流过来的水,水往低处流(选数值小的那个),流经当前格子时加上当前的过路费。”

    • 状态定义:f[i+1][j+1] 对应实际网格 (i, j) 的最小路径和。
    • 哨兵策略:
      • 墙壁:f 的第 0 行和第 0 列都被设为 Integer.MAX_VALUE。这代表“此路不通”(代价无穷大),迫使 Math.min 只能选择另一边的合法路径。
      • 入口:唯独 f[0][1] = 0。这是为了计算起点 (0,0) 时,min(MAX, 0) 能得到 0,从而正确初始化起点值为 0 + grid[0][0]。
    2. 算法流程 (DP 迭代)
  • 造墙 (Build Walls):
      • 创建 f[m+1][n+1]。
      • 将第 0 行 (f[0]) 全填满 MAX_VALUE。
      • 在循环内部,每处理一行,先将该行的第 0 列 (f[i+1][0]) 设为 MAX_VALUE。
  • 开门 (Open Door):
      • f[0][1] = 0。这是唯一的突破口,就像给起点“上方”开了一个免费的入口。
  • 填表 (Loop):
      • 遍历实际网格 (i, j)。
      • 核心转移:f[curr] = Math.min(f[left], f[up]) + grid[curr]。
      • 由于墙壁是 MAX,如果靠墙(比如第一行),up 是 MAX,min 就会自动选择 left(除非左边也是墙,那是起点的情况,由 f[0][1] 处理)。
  • 结果 (Result):
      • 返回 f[m][n]。
    🔍 代码回忆清单

    // 题目:LC 64. Minimum Path Sum
    class Solution {
    public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // 1. DP 表:多开一行一列 (Padding)
    int[][] f = new int[m + 1][n + 1];

    // 2. 初始化上方墙壁 (第0行) 为无穷大
    Arrays.fill(f[0], Integer.MAX_VALUE);

    // 3. 核心技巧:设置虚拟入口
    // 只有这里是 0,保证起点 (0,0) 的 min 计算结果为 0
    f[0][1] = 0;

    for (int i = 0; i < m; i++) {
    // 4. 初始化左侧墙壁 (第0列) 为无穷大
    // 必须在每一行开始时设置,或者一开始整个数组 fill MAX
    f[i + 1][0] = Integer.MAX_VALUE;

    for (int j = 0; j < n; j++) {
    // 5. 状态转移
    // min(左边, 上边) + 当前值
    // 遇到墙壁时,MAX_VALUE 会在 min 比较中落败,从而被过滤掉
    f[i + 1][j + 1] = Math.min(f[i + 1][j], f[i][j + 1]) + grid[i][j];
    }
    }

    return f[m][n];
    }
    }

    ⚡ 快速复习 CheckList (易错点)
    • [ ] 为什么 f[0][1] = 0 而不是 f[0][0]?
      • f[0][0] 处于“墙角”(左上角的左上角)。如果设为 0,它既不是起点的正左,也不是起点的正上,无法直接影响起点的计算。
      • f[0][1] 是起点的 正上方(在 DP 表的坐标系里),它直接参与 f[1][1] 的计算。
    • [ ] 会有整数溢出风险吗?
      • 代码中逻辑是 Math.min(MAX, valid) + grid。
      • Math.min 会选出 valid(较小值),然后加 grid。这是安全的。
      • 只有当网格完全不可达(不可能发生)导致 min 选了 MAX,再加 grid 才会溢出变成负数。
    • [ ] 为什么要在循环里写 f[i+1][0] = MAX?
      • 因为 Java 的 int[][] 默认初始化是 0。如果不手动设为 MAX,第 0 列就是 0(免费路径),计算第一列时就会错误地认为左边路不要钱。
    🖼️ 数字演练

    Grid = [[1, 3], [1, 5]] m=2, n=2.

  • 初始化:
      • f 表 (3×3)。
      • Row 0: [MAX, 0, MAX] (注意 f[0][1]=0)。
      • Row 1 & 2: 初始全 0。
  • i=0 (实际第1行):
      • Set f[1][0] = MAX (左墙)。
      • j=0 (起点 1): min(f[1][0]=MAX, f[0][1]=0) + 1 = 1。 f[1][1]=1。
      • j=1 (值 3): min(f[1][1]=1, f[0][2]=MAX) + 3 = 4。 f[1][2]=4。
      • Row 1 状态: [MAX, 1, 4]。
  • i=1 (实际第2行):
      • Set f[2][0] = MAX (左墙)。
      • j=0 (值 1): min(f[2][0]=MAX, f[1][1]=1) + 1 = 2。 f[2][1]=2。
      • j=1 (值 5): min(f[2][1]=2, f[1][2]=4) + 5 = 7。 f[2][2]=7。
      • Row 2 状态: [MAX, 2, 7]。
  • 最终结果: f[2][2] = 7。
  • 赞(0)
    未经允许不得转载:171主机测评 » 64. 最小路径和
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址