64. 最小路径和

记忆化搜索

---

一、算法逻辑（每一步思路）

❓ 题目简述：

给定一个 m × n 的二维网格 grid，每个位置都有一个非负整数，表示该格子的权值。要求从左上角 (0, 0) 出发，只能向 右 或 下 移动，走到右下角 (m-1, n-1)，求路径上的最小权值和。

---

✅ 解题思路（DFS + 记忆化）

1. 定义递归函数：

dfs(i, j) 表示：从起点 (0,0) 到达位置 (i,j) 的最小路径和。

2. 状态转移逻辑：

要走到 (i,j)，只能从：

• (i-1,j) 往下走过来，或
• (i,j-1) 往右走过来。

所以状态转移公式为：

dfs(i, j) = min(dfs(i-1, j), dfs(i, j-1)) + grid[i][j]

3. 边界条件：

• dfs(0, 0) = grid[0][0]，因为这是起点；
• i < 0 or j < 0：越界了，返回 inf 表示不可达。

4. 初始调用：

目标是从 (0,0) 到 (m-1, n-1)，所以直接返回 dfs(m-1, n-1)。

5. 记忆化缓存（@cache）：

避免重复计算重复状态，使递归从指数级降为多项式时间。

---

二、算法核心点

✅ 核心思想：二维网格路径型问题 + 记忆化搜索

• 问题结构是网格型最优路径；
• 使用 DFS 自顶向下拆解问题，每个位置的最优路径 = “前一步的最优 + 当前代价”；
• 因为状态有重叠（如多条路径都走到同一个 (i,j)），必须加缓存避免重复递归；
• 记忆化搜索是和 DP 等价的思想，但实现风格是递归式，更直观。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def dfs(i:int, j:int)->int:
            if i ==0 and j == 0:
                return grid[i][j]
            if i<0 or j<0:
                return inf
            return min((dfs(i,j-1)), dfs(i-1, j))+ grid[i][j]
        return dfs(len(grid)-1, len(grid[0])-1)

---

三、复杂度分析

• 时间复杂度：O(m × n)

• • 每个位置 (i,j) 的 dfs(i,j) 最多只算一次，缓存后复用；
  • 网格大小为 m × n，总状态数也为 m × n。

• 空间复杂度：O(m × n)

• • 用于缓存递归结果；
  • 递归栈深度最多为 m + n - 1。

---

总结表

维度	内容
✅ 思路逻辑	从起点出发递归查找所有路径最小和，向上/左两个方向递归，取较小值
✅ 核心技巧	记忆化搜索，状态定义为 (i,j) 的最短路径和，转移来自左边/上边的状态
✅ 时间复杂度	O(m × n)，每个位置只递归一次
✅ 空间复杂度	O(m × n)，缓存和递归栈空间

---

✅ 举个例子说明

grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

• 有三条路径从左上到右下，总和分别为：

• • 1 → 3 → 1 → 1 → 1 = 7
  • 1 → 3 → 5 → 1 → 1 = 11
  • 1 → 1 → 4 → 2 → 1 = 9

• 答案是最小值：7

递推写法

---

我们来系统分析这段代码，它是 LeetCode 64「最小路径和」（Minimum Path Sum）问题的二维动态规划（DP）解法，通过偏移索引简化边界处理，逻辑简洁、结构清晰。

---

一、算法逻辑（每一步思路）

❓ 问题描述：

给定一个 m x n 的网格 grid，每个格子有一个非负整数，表示从左上角 (0,0) 走到右下角 (m-1,n-1) 的路径，求路径上的最小路径和（只能向右或向下走）。

---

✅ 思路拆解（动态规划）

1. 定义状态：

• 定义 f[i][j] 表示：走到位置 (i-1, j-1) 的最小路径和。

注意这里 f 数组行列都偏移了 1，这样 f[1][1] 表示原 grid 的 grid[0][0]，目的是简化边界处理。

2. 初始化：

• 所有格子初始为 inf，表示不可达；
• 设定 f[0][1] = 0，配合状态转移可以让 f[1][1] = grid[0][0]。

3. 状态转移：

f[i+1][j+1] = min(f[i+1][j], f[i][j+1]) + x

• 当前格子的路径和 = 从左边或上边来的路径和中取较小的 + 当前格子的值 x（即 grid[i][j]）；
• f[i+1][j+1] 对应 grid[i][j]，f[i+1][j] 是左边，f[i][j+1] 是上边。

4. 返回结果：

最终走到 (m-1, n-1) 对应的是 f[m][n]。

---

二、算法核心点

✅ 核心思想：二维 DP + 偏移处理边界

• 每个状态只和它的左边和上边相关；
• 使用 f 数组偏移一位，避免特殊处理第一行第一列；
• 动态更新，每个格子只访问一次。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[inf] * (n + 1) for _ in range(m + 1)]
        f[0][1] = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1]) + x
        return f[m][n]

---

三、复杂度分析

• 时间复杂度：O(m × n)

• • 每个格子只访问并更新一次。

• 空间复杂度：O(m × n)

• • 二维数组 f 的大小为 (m+1) × (n+1)。

---

总结表

维度	内容
✅ 思路逻辑	从左上到右下，递推每个位置的最小路径和，状态来自左/上两个方向
✅ 核心技巧	二维 DP，状态定义清晰，索引偏移避免处理边界（无需 if 判断）
✅ 时间复杂度	O(m × n)
✅ 空间复杂度	O(m × n)

---

✅ 示例说明（部分 DP 表构造）

grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

其 DP 表（不偏移）如下所示：

1  4  5
2  7  6
6  8  7

最后结果是 7，路径为：1 → 3 → 1 → 1 → 1