Hello 算法 · 最小路径和问题从暴力搜索到空间优化动态规划的完整演进【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo最小路径和Minimum Path Sum是《Hello 算法》动态规划章节中用于演示「动态规划解题思路」的经典二维网格问题机器人从左上角出发每一步只能向下或向右求到达右下角所经过格子的最小代价总和。本文以仓库中该问题的 Python 实现为核心完整走一遍「暴力搜索 → 记忆化搜索 → 动态规划 → 空间优化」的演进路径讲解如何把一道网格题拆解为状态定义、状态转移方程、边界条件与转移顺序并给出可直接运行的代码与复杂度分析。读完本文你将掌握一套可复用到大多数二维 DP 问题的通用解题流水线。问题定义一题看清 DP 的全流程题目给定一个n × m的二维网格grid网格中的每个单元格包含一个非负整数表示该单元格的代价。机器人以左上角单元格为起始点每次只能向下或者向右移动一步直至到达右下角单元格。请返回从左上角到右下角的最小路径和。仓库中所有语言实现如 min_path_sum.py统一使用下面这个 4×4 的测试网格grid [[1, 3, 1, 5], [2, 2, 4, 2], [5, 3, 2, 1], [4, 3, 5, 2]]该网格的最小路径和为13求解过程对应章节 dp_solution_pipeline.md 中的图示数据。对这道题标准解法会经历三层递进先用 DFS 自顶向下枚举所有路径重叠子问题爆炸再用mem记忆表剪枝重复计算最后改写成自底向上的迭代 DP并进一步把二维dp表压缩为一行。这正是《Hello 算法》推荐的 DP 学习顺序。为什么它适合用动态规划求解问题判断方法先做定性判断。动态规划问题通常具备重叠子问题、最优子结构、无后效性三个特征但直接从题目文字提取这些特征并不容易所以书中的实用策略是放宽条件先观察问题是否适合用回溯穷举解决。适合用回溯解决的问题往往满足「决策树模型」——可以用树形结构描述问题每个节点是一次决策每条路径是一个决策序列。本题中机器人每一步都在「向下」与「向右」之间做出选择路径由一连串决策构成天然符合决策树模型。在此基础上再看是否有 DP 的「加分项」问题包含最大小/最多少等最优化描述——本题求「最小路径和」命中问题的状态能用列表、多维矩阵或树表示且状态与周围状态存在递推关系——本题状态[i, j]只依赖[i-1, j]与[i, j-1]命中。相应地也要检查「减分项」目标是找出所有可行方案而不是最优解本题只求一个最小值不命中问题有明显排列组合特征、需要返回多个具体方案本题不命中。因此可以假设它是 DP 问题进入求解环节并在推导中验证假设。推导骨架决策、状态、dp 表、转移方程与边界动态规划求解通常遵循五个步骤描述决策 → 定义状态 → 建立 dp 表 → 推导状态转移方程 → 确定边界条件与转移顺序。下面以本题为例逐步展开。第一步定义状态并建立 dp 表每一轮的决策是从当前格子向下或向右走一步。设当前格子的行列索引为[i, j]走一步后索引变为[i1, j]或[i, j1]因此状态必须同时包含行、列两个变量记为[i, j]。状态[i, j]对应的子问题是从起点[0, 0]走到[i, j]的最小路径和其解记为dp[i, j]。由此得到一张与输入grid同尺寸的二维dp表——状态中的每个独立变量都是 dp 表的一个维度。从本质上看dp 表就是「状态 → 子问题解」的映射它存下了所有子问题的答案供递推时反复取用。第二步找出最优子结构写出状态转移方程由于机器人只能从上方或左方进入[i, j]状态[i, j]只可能由[i-1, j]上边格子和[i, j-1]左边格子转移而来。最优子结构即到达[i, j]的最小路径和等于「上方最小路径和」与「左方最小路径和」中的较小者再加上当前格子的代价grid[i, j]$$ dp[i, j] \min(dp[i-1, j], dp[i, j-1]) grid[i, j] $$一旦找到「用子问题最优解构造原问题最优解」的最优子结构转移方程就顺理成章了。第三步确定边界条件与转移顺序首行i 0的格子没有上方来源只能从左方转移首列j 0的格子没有左方来源只能从上方转移。因此首行与首列是本题的边界条件用于初始化 dp 表在搜索写法中边界则用于控制递归的剪枝与终止。转移顺序的核心原则是计算某个状态时它所依赖的所有更小状态必须已经算好。由于每个格子依赖其左方与上方格子采用外层循环遍历行、内层循环遍历列的逐行扫描即可满足该依赖关系。方法一暴力搜索min_path_sum_dfs按「自顶向下」的直觉先写出递归枚举版本。它在库中的实现如下Python 源文件见 min_path_sum.pyfrom math import inf def min_path_sum_dfs(grid: list[list[int]], i: int, j: int) - int: 最小路径和暴力搜索完整枚举所有路径 # 若为左上角单元格则终止搜索 if i 0 and j 0: return grid[0][0] # 若行列索引越界返回 ∞ 代价表示此路不通 if i 0 or j 0: return inf # 分别计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价 up min_path_sum_dfs(grid, i - 1, j) left min_path_sum_dfs(grid, i, j - 1) # 返回从左上角到 (i, j) 的最小路径代价 return min(left, up) grid[i][j]递归函数的四个要素非常清晰要素取值递归参数状态[i, j]返回值从[0, 0]到[i, j]的最小路径和dp[i, j]终止条件i 0且j 0时返回grid[0][0]剪枝条件i 0或j 0时返回∞代表该方向不可行以状态dp[2, 1]为根节点的递归树如下图所示树中存在大量被重复计算的重叠子问题而且会随网格尺寸增大而急剧膨胀产生重叠子问题的根本原因是存在多条路径可以从左上角到达同一个单元格。每个状态都有向下、向右两种选择从左上角走到右下角共需m n - 2步因此最差时间复杂度为O(2^(mn))n、m分别为行数与列数实际路径数会略少因为到达边界后只剩一种选择。方法二记忆化搜索min_path_sum_dfs_mem暴力搜索慢在重复计算。引入一张与grid同尺寸的记忆表mem用-1表示「尚未计算」每次算出结果先存入表中再次遇到时直接查表返回从而剪掉重叠子问题def min_path_sum_dfs_mem( grid: list[list[int]], mem: list[list[int]], i: int, j: int ) - int: 最小路径和记忆化搜索 # 若为左上角单元格则终止搜索 if i 0 and j 0: return grid[0][0] # 若行列索引越界返回 ∞ 代价 if i 0 or j 0: return inf # 若记录已存在则直接返回 if mem[i][j] ! -1: return mem[i][j] # 左方和上方单元格的最小路径代价 up min_path_sum_dfs_mem(grid, mem, i - 1, j) left min_path_sum_dfs_mem(grid, mem, i, j - 1) # 记录并返回从左上角到 (i, j) 的最小路径代价 mem[i][j] min(left, up) grid[i][j] return mem[i][j]注意这里的边界处理当i 0或j 0时返回inf正是与「dp 表中首行首列需要特殊初始化」相对应的剪枝逻辑。引入记忆化后每个子问题的解只计算一次时间复杂度由递归树规模降为状态总数即O(nm)代价是额外O(nm)的记忆表空间。方法三动态规划min_path_sum_dp自顶向下的记忆化搜索本质上是递归版 DP。把它反转成「自底向上的迭代」就是标准动态规划写法先初始化 dp 表与首行、首列边界再按行从左到右填充其余状态def min_path_sum_dp(grid: list[list[int]]) - int: 最小路径和动态规划 n, m len(grid), len(grid[0]) # 初始化 dp 表 dp [[0] * m for _ in range(n)] dp[0][0] grid[0][0] # 状态转移首行 for j in range(1, m): dp[0][j] dp[0][j - 1] grid[0][j] # 状态转移首列 for i in range(1, n): dp[i][0] dp[i - 1][0] grid[i][0] # 状态转移其余行列 for i in range(1, n): for j in range(1, m): dp[i][j] min(dp[i][j - 1], dp[i - 1][j]) grid[i][j] return dp[n - 1][m - 1]三个循环分别处理三类格子首个格子dp[0][0] grid[0][0]即起点本身首行j 1的格子只能从左累加dp[0][j] dp[0][j-1] grid[0][j]首列i 1的格子只能从上累加dp[i][0] dp[i-1][0] grid[i][0]其余格子套用转移方程dp[i][j] min(dp[i][j-1], dp[i-1][j]) grid[i][j]。迭代过程会完整遍历整个网格时间复杂度为O(nm)二维dp表占据n × m空间空间复杂度为O(nm)。方法四空间优化——单行滚动数组min_path_sum_dp_comp观察转移方程可以发现dp[i][j]只依赖本行左侧dp[i][j-1]与上一行同列dp[i-1][j]。也就是说每一行的计算只需「上一行」的数据更早的行不再需要。因此可以把二维 dp 表压缩为长度m的一维数组逐行原地更新。有一个实现细节需要注意一维dp只能表示「当前行」的状态无法像二维版那样提前把整列首列初始化好所以首列状态要在遍历每一行时实时更新def min_path_sum_dp_comp(grid: list[list[int]]) - int: 最小路径和动态规划空间优化版 n, m len(grid), len(grid[0]) # 初始化 dp 表 dp [0] * m # 状态转移首行 dp[0] grid[0][0] for j in range(1, m): dp[j] dp[j - 1] grid[0][j] # 状态转移其余行 for i in range(1, n): # 状态转移首列 dp[0] dp[0] grid[i][0] # 状态转移其余列 for j in range(1, m): dp[j] min(dp[j - 1], dp[j]) grid[i][j] return dp[m - 1]更新dp[j]时等号右侧的dp[j]仍是上一行同列的结果尚未被覆盖dp[j-1]则是本行已更新过的左侧结果——两者恰好对应转移方程中的dp[i-1][j]与dp[i][j-1]。滚动更新让空间复杂度降为O(m)仅一行时间复杂度不变仍为O(nm)。四种方法复杂度对照与运行验证将四种解法汇总对比如下方法实现函数时间复杂度空间复杂度核心思想暴力搜索min_path_sum_dfsO(2^(mn))O(mn)递归栈从代码结构看栈深不超过路径步数自顶向下枚举全部路径记忆化搜索min_path_sum_dfs_memO(nm)O(nm)记忆表剪枝重叠子问题动态规划min_path_sum_dpO(nm)O(nm)自底向上迭代填表空间优化 DPmin_path_sum_dp_compO(nm)O(m)单行滚动数组原地更新源文件末尾的 Driver Code 把四种解法串在同一份grid上依次调用并打印结果见 min_path_sum.pyDriver Code if __name__ __main__: grid [[1, 3, 1, 5], [2, 2, 4, 2], [5, 3, 2, 1], [4, 3, 5, 2]] n, m len(grid), len(grid[0]) # 暴力搜索 res min_path_sum_dfs(grid, n - 1, m - 1) print(f从左上角到右下角的最小路径和为 {res}) # 记忆化搜索 mem [[-1] * m for _ in range(n)] res min_path_sum_dfs_mem(grid, mem, n - 1, m - 1) print(f从左上角到右下角的最小路径和为 {res}) # 动态规划 res min_path_sum_dp(grid) print(f从左上角到右下角的最小路径和为 {res}) # 空间优化动态规划 res min_path_sum_dp_comp(grid) print(f从左上角到右下角的最小路径和为 {res})直接运行即可复现结果python3 codes/python/chapter_dynamic_programming/min_path_sum.py四种方法会输出一致的答案13与书中「给定网格的最小路径和为 13」的结论相互印证——这也是检验递推改写是否引入错误的最简单手段。仓库中的配套资源与延伸阅读如果你想把这套思路迁移到其他语言或继续深入仓库提供了完整的配套材料章节正文讲解dp_solution_pipeline.md 用最小路径和完整演示了「问题判断 → 状态定义 → 转移方程 → 边界条件」的解题流水线并配有状态定义、转移方程、DP 分步填充step1–step12等插图Python 可视化执行min_path_sum.md俄语版见 ru 对应文件收录了四个函数在 PythonTutor 上的交互式逐步执行链接其 HTML 注释标识[file]{min_path_sum}-[func]{...}与章节正文的代码引用一一对应方便边看边调试递归与填表过程多语言同款实现同一套算法在 C、Java、Go、C、Rust、TypeScript 等十余种语言中均有对应文件函数命名与 Python 版保持一致可作为语言对照学习的范本。最小路径和之所以适合作为 DP 入门例题是因为它把「二维状态如何定义、转移依赖如何排列、边界如何初始化」全部浓缩在一个网格中。掌握从暴力搜索到滚动数组的这条演进链再去啃背包问题、编辑距离等更复杂的二维 DP仓库 chapter_dynamic_programming 下均有实现就能举一反三、触类旁通。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/8 18:07:06 · 阅读 1.2k Hello 算法 · 最小路径和问题：从暴力搜索到空间优化动态规划的完整演进
Hello 算法 · 最小路径和问题从暴力搜索到空间优化动态规划的完整演进【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo最小路径和Minimum Path Sum是《Hello 算法》动态规划章节中用于演示「动态规划解题思路」的经典二维网格问题机器人从左上角出发每一步只能向下或向右求到达右下角所经过格子的最小代价总和。本文以仓库中该问题的 Python 实现为核心完整走一遍「暴力搜索 → 记忆化搜索 → 动态规划 → 空间优化」的演进路径讲解如何把一道网格题拆解为状态定义、状态转移方程、边界条件与转移顺序并给出可直接运行的代码与复杂度分析。读完本文你将掌握一套可复用到大多数二维 DP 问题的通用解题流水线。问题定义一题看清 DP 的全流程题目给定一个n × m的二维网格grid网格中的每个单元格包含一个非负整数表示该单元格的代价。机器人以左上角单元格为起始点每次只能向下或者向右移动一步直至到达右下角单元格。请返回从左上角到右下角的最小路径和。仓库中所有语言实现如 min_path_sum.py统一使用下面这个 4×4 的测试网格grid [[1, 3, 1, 5], [2, 2, 4, 2], [5, 3, 2, 1], [4, 3, 5, 2]]该网格的最小路径和为13求解过程对应章节 dp_solution_pipeline.md 中的图示数据。对这道题标准解法会经历三层递进先用 DFS 自顶向下枚举所有路径重叠子问题爆炸再用mem记忆表剪枝重复计算最后改写成自底向上的迭代 DP并进一步把二维dp表压缩为一行。这正是《Hello 算法》推荐的 DP 学习顺序。为什么它适合用动态规划求解问题判断方法先做定性判断。动态规划问题通常具备重叠子问题、最优子结构、无后效性三个特征但直接从题目文字提取这些特征并不容易所以书中的实用策略是放宽条件先观察问题是否适合用回溯穷举解决。适合用回溯解决的问题往往满足「决策树模型」——可以用树形结构描述问题每个节点是一次决策每条路径是一个决策序列。本题中机器人每一步都在「向下」与「向右」之间做出选择路径由一连串决策构成天然符合决策树模型。在此基础上再看是否有 DP 的「加分项」问题包含最大小/最多少等最优化描述——本题求「最小路径和」命中问题的状态能用列表、多维矩阵或树表示且状态与周围状态存在递推关系——本题状态[i, j]只依赖[i-1, j]与[i, j-1]命中。相应地也要检查「减分项」目标是找出所有可行方案而不是最优解本题只求一个最小值不命中问题有明显排列组合特征、需要返回多个具体方案本题不命中。因此可以假设它是 DP 问题进入求解环节并在推导中验证假设。推导骨架决策、状态、dp 表、转移方程与边界动态规划求解通常遵循五个步骤描述决策 → 定义状态 → 建立 dp 表 → 推导状态转移方程 → 确定边界条件与转移顺序。下面以本题为例逐步展开。第一步定义状态并建立 dp 表每一轮的决策是从当前格子向下或向右走一步。设当前格子的行列索引为[i, j]走一步后索引变为[i1, j]或[i, j1]因此状态必须同时包含行、列两个变量记为[i, j]。状态[i, j]对应的子问题是从起点[0, 0]走到[i, j]的最小路径和其解记为dp[i, j]。由此得到一张与输入grid同尺寸的二维dp表——状态中的每个独立变量都是 dp 表的一个维度。从本质上看dp 表就是「状态 → 子问题解」的映射它存下了所有子问题的答案供递推时反复取用。第二步找出最优子结构写出状态转移方程由于机器人只能从上方或左方进入[i, j]状态[i, j]只可能由[i-1, j]上边格子和[i, j-1]左边格子转移而来。最优子结构即到达[i, j]的最小路径和等于「上方最小路径和」与「左方最小路径和」中的较小者再加上当前格子的代价grid[i, j]$$ dp[i, j] \min(dp[i-1, j], dp[i, j-1]) grid[i, j] $$一旦找到「用子问题最优解构造原问题最优解」的最优子结构转移方程就顺理成章了。第三步确定边界条件与转移顺序首行i 0的格子没有上方来源只能从左方转移首列j 0的格子没有左方来源只能从上方转移。因此首行与首列是本题的边界条件用于初始化 dp 表在搜索写法中边界则用于控制递归的剪枝与终止。转移顺序的核心原则是计算某个状态时它所依赖的所有更小状态必须已经算好。由于每个格子依赖其左方与上方格子采用外层循环遍历行、内层循环遍历列的逐行扫描即可满足该依赖关系。方法一暴力搜索min_path_sum_dfs按「自顶向下」的直觉先写出递归枚举版本。它在库中的实现如下Python 源文件见 min_path_sum.pyfrom math import inf def min_path_sum_dfs(grid: list[list[int]], i: int, j: int) - int: 最小路径和暴力搜索完整枚举所有路径 # 若为左上角单元格则终止搜索 if i 0 and j 0: return grid[0][0] # 若行列索引越界返回 ∞ 代价表示此路不通 if i 0 or j 0: return inf # 分别计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价 up min_path_sum_dfs(grid, i - 1, j) left min_path_sum_dfs(grid, i, j - 1) # 返回从左上角到 (i, j) 的最小路径代价 return min(left, up) grid[i][j]递归函数的四个要素非常清晰要素取值递归参数状态[i, j]返回值从[0, 0]到[i, j]的最小路径和dp[i, j]终止条件i 0且j 0时返回grid[0][0]剪枝条件i 0或j 0时返回∞代表该方向不可行以状态dp[2, 1]为根节点的递归树如下图所示树中存在大量被重复计算的重叠子问题而且会随网格尺寸增大而急剧膨胀产生重叠子问题的根本原因是存在多条路径可以从左上角到达同一个单元格。每个状态都有向下、向右两种选择从左上角走到右下角共需m n - 2步因此最差时间复杂度为O(2^(mn))n、m分别为行数与列数实际路径数会略少因为到达边界后只剩一种选择。方法二记忆化搜索min_path_sum_dfs_mem暴力搜索慢在重复计算。引入一张与grid同尺寸的记忆表mem用-1表示「尚未计算」每次算出结果先存入表中再次遇到时直接查表返回从而剪掉重叠子问题def min_path_sum_dfs_mem( grid: list[list[int]], mem: list[list[int]], i: int, j: int ) - int: 最小路径和记忆化搜索 # 若为左上角单元格则终止搜索 if i 0 and j 0: return grid[0][0] # 若行列索引越界返回 ∞ 代价 if i 0 or j 0: return inf # 若记录已存在则直接返回 if mem[i][j] ! -1: return mem[i][j] # 左方和上方单元格的最小路径代价 up min_path_sum_dfs_mem(grid, mem, i - 1, j) left min_path_sum_dfs_mem(grid, mem, i, j - 1) # 记录并返回从左上角到 (i, j) 的最小路径代价 mem[i][j] min(left, up) grid[i][j] return mem[i][j]注意这里的边界处理当i 0或j 0时返回inf正是与「dp 表中首行首列需要特殊初始化」相对应的剪枝逻辑。引入记忆化后每个子问题的解只计算一次时间复杂度由递归树规模降为状态总数即O(nm)代价是额外O(nm)的记忆表空间。方法三动态规划min_path_sum_dp自顶向下的记忆化搜索本质上是递归版 DP。把它反转成「自底向上的迭代」就是标准动态规划写法先初始化 dp 表与首行、首列边界再按行从左到右填充其余状态def min_path_sum_dp(grid: list[list[int]]) - int: 最小路径和动态规划 n, m len(grid), len(grid[0]) # 初始化 dp 表 dp [[0] * m for _ in range(n)] dp[0][0] grid[0][0] # 状态转移首行 for j in range(1, m): dp[0][j] dp[0][j - 1] grid[0][j] # 状态转移首列 for i in range(1, n): dp[i][0] dp[i - 1][0] grid[i][0] # 状态转移其余行列 for i in range(1, n): for j in range(1, m): dp[i][j] min(dp[i][j - 1], dp[i - 1][j]) grid[i][j] return dp[n - 1][m - 1]三个循环分别处理三类格子首个格子dp[0][0] grid[0][0]即起点本身首行j 1的格子只能从左累加dp[0][j] dp[0][j-1] grid[0][j]首列i 1的格子只能从上累加dp[i][0] dp[i-1][0] grid[i][0]其余格子套用转移方程dp[i][j] min(dp[i][j-1], dp[i-1][j]) grid[i][j]。迭代过程会完整遍历整个网格时间复杂度为O(nm)二维dp表占据n × m空间空间复杂度为O(nm)。方法四空间优化——单行滚动数组min_path_sum_dp_comp观察转移方程可以发现dp[i][j]只依赖本行左侧dp[i][j-1]与上一行同列dp[i-1][j]。也就是说每一行的计算只需「上一行」的数据更早的行不再需要。因此可以把二维 dp 表压缩为长度m的一维数组逐行原地更新。有一个实现细节需要注意一维dp只能表示「当前行」的状态无法像二维版那样提前把整列首列初始化好所以首列状态要在遍历每一行时实时更新def min_path_sum_dp_comp(grid: list[list[int]]) - int: 最小路径和动态规划空间优化版 n, m len(grid), len(grid[0]) # 初始化 dp 表 dp [0] * m # 状态转移首行 dp[0] grid[0][0] for j in range(1, m): dp[j] dp[j - 1] grid[0][j] # 状态转移其余行 for i in range(1, n): # 状态转移首列 dp[0] dp[0] grid[i][0] # 状态转移其余列 for j in range(1, m): dp[j] min(dp[j - 1], dp[j]) grid[i][j] return dp[m - 1]更新dp[j]时等号右侧的dp[j]仍是上一行同列的结果尚未被覆盖dp[j-1]则是本行已更新过的左侧结果——两者恰好对应转移方程中的dp[i-1][j]与dp[i][j-1]。滚动更新让空间复杂度降为O(m)仅一行时间复杂度不变仍为O(nm)。四种方法复杂度对照与运行验证将四种解法汇总对比如下方法实现函数时间复杂度空间复杂度核心思想暴力搜索min_path_sum_dfsO(2^(mn))O(mn)递归栈从代码结构看栈深不超过路径步数自顶向下枚举全部路径记忆化搜索min_path_sum_dfs_memO(nm)O(nm)记忆表剪枝重叠子问题动态规划min_path_sum_dpO(nm)O(nm)自底向上迭代填表空间优化 DPmin_path_sum_dp_compO(nm)O(m)单行滚动数组原地更新源文件末尾的 Driver Code 把四种解法串在同一份grid上依次调用并打印结果见 min_path_sum.pyDriver Code if __name__ __main__: grid [[1, 3, 1, 5], [2, 2, 4, 2], [5, 3, 2, 1], [4, 3, 5, 2]] n, m len(grid), len(grid[0]) # 暴力搜索 res min_path_sum_dfs(grid, n - 1, m - 1) print(f从左上角到右下角的最小路径和为 {res}) # 记忆化搜索 mem [[-1] * m for _ in range(n)] res min_path_sum_dfs_mem(grid, mem, n - 1, m - 1) print(f从左上角到右下角的最小路径和为 {res}) # 动态规划 res min_path_sum_dp(grid) print(f从左上角到右下角的最小路径和为 {res}) # 空间优化动态规划 res min_path_sum_dp_comp(grid) print(f从左上角到右下角的最小路径和为 {res})直接运行即可复现结果python3 codes/python/chapter_dynamic_programming/min_path_sum.py四种方法会输出一致的答案13与书中「给定网格的最小路径和为 13」的结论相互印证——这也是检验递推改写是否引入错误的最简单手段。仓库中的配套资源与延伸阅读如果你想把这套思路迁移到其他语言或继续深入仓库提供了完整的配套材料章节正文讲解dp_solution_pipeline.md 用最小路径和完整演示了「问题判断 → 状态定义 → 转移方程 → 边界条件」的解题流水线并配有状态定义、转移方程、DP 分步填充step1–step12等插图Python 可视化执行min_path_sum.md俄语版见 ru 对应文件收录了四个函数在 PythonTutor 上的交互式逐步执行链接其 HTML 注释标识[file]{min_path_sum}-[func]{...}与章节正文的代码引用一一对应方便边看边调试递归与填表过程多语言同款实现同一套算法在 C、Java、Go、C、Rust、TypeScript 等十余种语言中均有对应文件函数命名与 Python 版保持一致可作为语言对照学习的范本。最小路径和之所以适合作为 DP 入门例题是因为它把「二维状态如何定义、转移依赖如何排列、边界如何初始化」全部浓缩在一个网格中。掌握从暴力搜索到滚动数组的这条演进链再去啃背包问题、编辑距离等更复杂的二维 DP仓库 chapter_dynamic_programming 下均有实现就能举一反三、触类旁通。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考