Hello 算法：动态规划五步解题流程详解——以“最小路径和”为例的暴力搜索、记忆化与空间优化实战

本文基于 hello-algo 仓库《Hello 算法》的动态规划章节，系统讲解“如何判断一个问题适合动态规划”以及“动态规划完整求解步骤”这两个核心问题，并以经典问题“最小路径和”为主线，完整演示从定义状态、推导状态转移方程、确定边界条件，到暴力搜索、记忆化搜索、动态规划迭代、一维数组空间优化的全链路实现。读完本文，你将掌握一套可复用的 DP 问题判别与求解方法论，并能在仓库的 Python / C++ / Go / Java 等多语言实现中找到对应源码进行验证。

一、问题判断：先问“能不能回溯”，再看 DP 加分项

动态规划的经典特征是重叠子问题、最优子结构、无后效性，但这些特征很难从问题描述中直接看出来。因此《Hello 算法》给出了一条更务实的判别路径：先观察问题是否适合使用回溯（穷举）解决。

适合用回溯解决的问题通常满足**“决策树模型”**——问题可以用一棵树来描述，树中每个节点代表一个决策，每条路径代表一个决策序列。换句话说：如果问题包含明确的“决策”概念，且最终解是由一系列决策逐步产生的，那么它就满足决策树模型，通常可以先用回溯解决。

在此基础上，判断是否进一步使用动态规划，可以参照以下“加分项”与“减分项”：

加分项（倾向于 DP）：

• 问题包含“最大 / 最小”“最多 / 最少”等最优化描述；
• 问题的状态能够用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态之间存在递推关系。

减分项（不倾向于 DP）：

• 问题的目标是找出所有可能的解决方案，而不是找最优解；
• 问题描述中有明显的排列组合特征，需要返回具体的多个方案。

结论：如果一个问题满足决策树模型，且具有较为明显的加分项，就可以假设它是动态规划问题，然后在求解过程中加以验证——验证手段正是下面要介绍的“暴力搜索 → 记忆化搜索 → 动态规划”实现顺序。

二、动态规划求解的五个步骤

动态规划的解题流程虽因问题性质而异，但通常遵循以下固定管线：

1. 描述决策：明确每一轮有哪些可选动作；
2. 定义状态：用决策变量刻画“解题进度”，每个状态对应一个子问题；
3. 建立 dp 表：以状态变量为维度构造表格，存储所有子问题的解；
4. 推导状态转移方程：找出最优子结构，用子问题最优解构造原问题最优解；
5. 确定边界条件与状态转移顺序：初始化 dp 表，并保证计算某状态时其依赖的子问题已先算出。

为了形象展示这套流程，仓库选用经典问题“最小路径和”来举例（源码见 codes/python/chapter_dynamic_programming/min_path_sum.py）。

问题描述

给定一个 $n \times m$ 的二维网格 grid，每个单元格包含一个非负整数，表示进入该单元格的代价。机器人从左上角 [0, 0] 出发，每次只能向下或向右移动一步，直至到达右下角。求从左上角到右下角的最小路径和。

仓库中四种语言的测试数据均为 4x4 网格，其最小路径和为 13：

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

第一步：定义决策与状态，得到 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-1, j] 和左边格子 [i, j-1] 转移而来，因此最优子结构为：到达 [i, j] 的最小路径和，由 [i-1, j] 与 [i, j-1] 两个子问题解中较小的那个加上当前格子代价决定。据此得到状态转移方程：

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

思考顺序是：先按定义好的 dp 表思考原问题与子问题的关系，找出“用子问题最优解构造原问题最优解”的方法（即最优子结构），再把它翻译成状态转移方程。

第三步：确定边界条件与状态转移顺序

本题中，处在首行（i = 0）的状态只能从左边转移而来，处在首列（j = 0）的状态只能从上边转移而来，所以首行与首列就是边界条件。

状态转移顺序的核心原则是：计算当前问题的解时，所有它依赖的更小子问题的解必须已经算出。由于每个格子依赖其左方和上方格子，采用“外循环遍历各行、内循环遍历各列”的顺序即可保证该依赖成立。

补充一点概念：边界条件在动态规划中用于初始化 dp 表，在搜索中则用于剪枝——同一个概念在两种实现形态下各司其职。

三、方法一：暴力搜索（自顶向下的状态分解）

子问题分解是从顶至底的思想，因此先按回溯方式实现。从状态 [i, j] 出发不断分解为更小的 [i-1, j] 和 [i, j-1]，递归函数包含四个要素：

• 递归参数：状态 [i, j]；
• 返回值：从 [0, 0] 到 [i, j] 的最小路径和 dp[i][j]；
• 终止条件：i == 0 且 j == 0 时返回 grid[0][0]；
• 剪枝：i < 0 或 j < 0 时索引越界，返回 $+\infty$ 代价代表不可行。

仓库 Python 实现（min_path_sum.py）完整体现了上述四要素：

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]

其他语言的实现结构与注释一致，例如 C++ 中越界返回 INT_MAX（min_path_sum.cpp），Go 中越界返回 math.MaxInt（min_path_sum.go）。

从递归树可以直观看到重叠子问题的存在，其数量随网格尺寸急剧增多。从本质上看，重叠的根源是：存在多条路径可以从左上角到达某一单元格。

时间复杂度方面：每个状态都有向下、向右两种选择，从左上角走到右下角共需 $m + n - 2$ 步，因此最差时间复杂度为 $O(2^{m+n})$（$n$、$m$ 分别为网格行数与列数）。需要注意，该计算未考虑临近网格边界时只剩一种选择的情况，实际路径数会少一些，但指数级增长的趋势不变。

四、方法二：记忆化搜索（用空间换时间）

针对重叠子问题，引入一个与 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]

调用前需要初始化记忆表（见 驱动代码）：mem = [[-1] * m for _ in range(n)]。

引入记忆化后，所有子问题的解只需计算一次，时间复杂度退化为状态总数，即 $O(nm)$；空间复杂度同样为 $O(nm)$（mem 表加上递归栈深度）。Go 的测试用例 min_path_sum_test.go 中同样按行初始化 -1 填充的 mem 矩阵，验证了这一初始化要求。

五、方法三：动态规划（自底向上的迭代）

既然状态转移只依赖“上方”和“左方”，就可以把递归翻转为双层循环的迭代实现：

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 表”，双重循环对应“状态转移顺序”，循环体则是状态转移方程 dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j] 的直接落地。

复杂度：遍历整个网格，时间复杂度 $O(nm)$；dp 数组大小为 $n \times m$，空间复杂度 $O(nm)$。

仓库中四种语言的 DP 实现逻辑完全对齐：Python（min_path_sum.py）、C++（min_path_sum.cpp）、Go（min_path_sum.go）、Java（min_path_sum.java），可以相互对照阅读以确认状态转移写法的一致性。

六、空间优化：一维滚动数组

由于每个格子只与其左边和上边的格子有关，dp 表可以压缩为单行数组。关键在于理解一维数组的“时间语义”：

• 遍历到第 i 行、第 j 列时，dp[j] 中存的还是上一行（即 i-1 行）第 j 列的值，恰好充当 dp[i-1][j]；
• dp[j-1] 则已在本行被更新过，恰好充当 dp[i][j-1]。

因此 dp[j] = min(dp[j-1], dp[j]) + grid[i][j] 中，dp[j]（旧值）扮演“上方”，dp[j-1]（新值）扮演“左方”。

由于一维数组只能表示一行的状态，无法像二维版那样提前初始化首列，只能在遍历每行时即时更新首列元素：

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[0] = dp[0] + grid[i][0] 这一行：首列没有“左方”可转移，只能沿“上方”（即 dp[0] 的旧值）累加，这正是文档中“首列状态在遍历每行时更新它”的体现。C++ 与 Go 版本写法一致（min_path_sum.cpp、min_path_sum.go）。优化后空间复杂度降为 $O(m)$，时间复杂度仍为 $O(nm)$。

七、小结：一套可复用的 DP 解题管线

把全文串起来，动态规划的工程化求解路径是：

步骤	最小路径和中的对应物
判断问题	满足决策树模型 + 最优化描述（“最小路径和”）→ 假设是 DP 问题
定义状态	dp[i][j]：从 [0,0] 到 [i,j] 的最小路径和
状态转移方程	dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
边界条件	首行只由左方累加、首列只由上方累加
转移顺序	外层行、内层列，保证依赖项先算出
实现形态	暴力搜索 $O(2^{m+n})$ → 记忆化 $O(nm)$ → 迭代 DP $O(nm)$ → 滚动数组 $O(m)$ 空间

仓库为这条管线提供了完整的验证入口：运行 codes/python/chapter_dynamic_programming/min_path_sum.py 的驱动代码，四种方法会依次在同一 4x4 网格上输出相同的最小路径和 13；Go 侧则可通过 min_path_sum_test.go 在测试框架中复核。当你面对一个新的 DP 问题时，套用“先回溯建模、再加分项判断、最后按五步展开”的流程，就可以系统地把它求解出来。