多维动态规划题解——最小路径和【LeetCode】记忆化搜索翻译为递推写法
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:@cachedef dfs(i:int, j:int)->int:if i ==0 and j == 0:return grid[i][j]if i<0 or j<0:return infreturn 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] = 0for 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]) + xreturn 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