企业官网建设流程全解析

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]，走一步后索引变为[i+1, j]或[i, j+1]，因此状态必须同时包含行、列两个变量，记为[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.py）：

from 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]

递归函数的四个要素非常清晰：

以状态dp[2, 1]为根节点的递归树如下图所示，树中存在大量被重复计算的重叠子问题，而且会随网格尺寸增大而急剧膨胀：

产生重叠子问题的根本原因是：存在多条路径可以从左上角到达同一个单元格。每个状态都有向下、向右两种选择，从左上角走到右下角共需m + n - 2步，因此最差时间复杂度为O(2^(m+n))（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)。

四种方法复杂度对照与运行验证

将四种解法汇总对比如下：

源文件末尾的 Driver Code 把四种解法串在同一份grid上依次调用并打印结果（见 min_path_sum.py）：

"""Driver 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