Part 5.7：DP 总结与方法论

引言：从”恐惧”到”掌握”

动态规划（Dynamic Programming, DP）是算法学习中的一座大山。很多人在初次接触 DP 时，都会被其抽象的状态定义、复杂的状态转移方程和多样的题型所震慑，甚至产生”DP 太难了”的畏惧心理。

但事实上，DP 并不是一种”神秘的魔法”，而是一种系统化的思维方式。它有着清晰的理论基础（最优子结构、重叠子问题）、固定的解题步骤（定义状态、推导转移方程、确定边界条件、确定计算顺序）和可复用的代码模板。

在前面的六篇文章中，我们系统地学习了 DP 的各个分支：

✅ Part 5.1：DP 入门：背包问题
✅ Part 5.2：最长上升子序列 (LIS)
✅ Part 5.3：最长公共子序列 (LCS)
✅ Part 5.4：区间 DP
✅ Part 5.5：树形 DP
✅ Part 5.6：状态压缩 DP

本文将作为整个 DP 系列的收官之作，为你提炼出一套通用的 DP 方法论，帮助你从”做题”升华到”掌握思维模式”，让你在面对任何 DP 问题时，都能从容应对。

一、如何识别一个问题是 DP 问题？

在解决一个问题之前，首先要判断它是否适合用 DP 来解决。以下是一些关键的识别标志：

1. 问题具有”最优子结构”

定义：一个问题的最优解包含其子问题的最优解。

直觉：如果你能用”如果我知道了子问题的最优解，我就能推导出原问题的最优解”这样的逻辑来思考，那么它很可能具有最优子结构。

例子：

背包问题：前 i 件物品的最优方案，必然包含前 i-1 件物品的某个最优方案。
最短路径：从 A 到 C 的最短路径，如果经过 B，那么 A 到 B 和 B 到 C 的路径也必然是各自的最短路径。

2. 问题具有”重叠子问题”

定义：在递归求解的过程中，许多相同的子问题会被反复计算多次。

直觉：如果你用递归暴力求解时，发现同样的参数组合被反复调用，那么它就有重叠子问题。

例子：

斐波那契数列：计算 fib(5) 时，fib(3) 会被计算多次。
背包问题：在考虑不同物品时，会多次遇到”背包容量为 w 时的最优解”这个子问题。

3. 问题要求”最优解”或”计数”

DP 通常用于求解以下类型的问题：

最优化问题：求最大值、最小值、最长、最短等。
计数问题：求方案数、路径数等。

关键词：最大、最小、最长、最短、有多少种方式、是否可能等。

4. 问题具有”无后效性”

定义：当前状态的决策只依赖于已知的状态，而不依赖于未来的决策。

直觉：一旦某个状态确定，它的值就不会再因为后续的决策而改变。

反例：如果问题中存在”后悔”机制（即后续决策会影响之前的状态），那么它可能不适合用标准 DP 求解。

二、DP 问题的通用解题步骤

一旦确定了问题可以用 DP 解决，接下来就是按照以下五个步骤来构建解法：

步骤 1：定义状态 (State Definition)

这是 DP 中最关键、也是最难的一步。

核心问题：我需要用什么信息来描述一个子问题？

常见的状态定义模式：

一维状态：dp[i] 表示与前 i 个元素相关的最优解。
- 例：dp[i] = 以第 i 个元素结尾的最长上升子序列长度。
二维状态：dp[i][j] 表示与两个维度相关的最优解。
- 例：dp[i][j] = 前 i 个物品在容量为 j 的背包中的最大价值。
- 例：dp[i][j] = 字符串 s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度。
区间状态：dp[i][j] 表示区间 [i, j] 的最优解。
- 例：dp[i][j] = 合并区间 [i, j] 内所有石子的最小成本。
树形状态：dp[u][state] 表示以节点 u 为根的子树在某种状态下的最优解。
- 例：dp[u][0/1] = 节点 u 不选/选时，其子树的最大权值。
状态压缩：dp[mask][i] 表示访问状态为 mask，当前在位置 i 的最优解。
- 例：dp[mask][i] = 访问了 mask 集合的城市，当前在城市 i 的最短路径。

技巧：

状态定义要完整：能够唯一确定一个子问题。
状态定义要无冗余：不包含不必要的信息。
可以尝试多种定义，选择最容易推导转移方程的那个。

步骤 2：推导状态转移方程 (State Transition)

核心问题：当前状态 dp[...] 如何从之前的状态推导而来？

思考方式：

决策分析：在当前状态下，我有哪些决策选项？每种决策会导致什么结果？
子问题分解：当前问题可以分解为哪些更小的子问题？

常见的转移模式：

选或不选：dp[i] = max(不选第i个, 选第i个)
- 例：背包问题 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
从前面转移：dp[i] = f(dp[j]) for j < i
- 例：LIS dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]
区间合并：dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost) for k in [i, j)
- 例：石子合并
树形递推：dp[u] = f(dp[v]) for all children v of u
- 例：树形 DP

步骤 3：确定边界条件 (Base Case)

核心问题：哪些状态是已知的、不需要计算的？

常见的边界条件：

dp[0][...] = 0 或某个初始值（表示”没有元素”的情况）
dp[i][0] = 0 或某个初始值（表示”容量/长度为0”的情况）
dp[i][i] = ...（表示单个元素的情况）

注意：边界条件的设置必须与状态定义和转移方程保持一致。

步骤 4：确定计算顺序 (Computation Order)

核心问题：我应该按照什么顺序来填充 DP 表，才能保证在计算当前状态时，所依赖的子状态已经被计算？

常见的计算顺序：

线性 DP：从前往后遍历 i。
二维 DP：通常是两层循环，先 i 后 j。
区间 DP：必须按区间长度 len 从小到大遍历。
树形 DP：通过 DFS（后序遍历）自然地实现自底向上的计算。
状态压缩 DP：按 mask 从小到大遍历（因为小的 mask 是大的 mask 的子集）。

步骤 5：实现与优化

实现：根据前面的分析，写出代码。
优化：
- 空间优化：如果 dp[i] 只依赖于 dp[i-1]，可以用滚动数组或一维数组优化空间。
- 时间优化：通过数据结构（如单调队列、线段树）优化状态转移的时间复杂度。

三、DP 的常见分类与模板

1. 线性 DP

特点：状态在一维或二维的线性空间上转移。

模板：

# 一维线性 DP
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
    dp[i] = f(dp[j] for j < i)

代表问题：LIS、爬楼梯、打家劫舍。

2. 背包 DP

特点：涉及”选或不选”的决策，通常有容量限制。

模板：

# 0-1 背包
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, W + 1):
        if j < weight[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1])

代表问题：0-1 背包、完全背包、多重背包。

3. 区间 DP

特点：状态定义在一个区间 [i, j] 上，通过枚举分割点 k 来转移。

模板：

dp = [[0] * n for _ in range(n)]
# 初始化 dp[i][i]
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + cost for k in range(i, j))

代表问题：石子合并、矩阵链乘法、最长回文子序列。

4. 树形 DP

特点：在树形结构上进行 DP，通过 DFS（后序遍历）实现状态转移。

模板：

def dfs(u):
    dp[u][0] = ...
    dp[u][1] = ...
    for v in children[u]:
        dfs(v)
        dp[u][0] += f(dp[v])
        dp[u][1] += g(dp[v])

代表问题：树的最大独立集、树的直径、树的重心。

5. 状态压缩 DP

特点：用二进制位表示集合状态，适用于 n <= 20 的组合优化问题。

模板：

dp = [[inf] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(1, 1 << n):
    for i in range(n):
        if (mask >> i) & 1:
            for j in range(n):
                if j != i and (mask >> j) & 1:
                    prev_mask = mask ^ (1 << i)
                    dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + cost[j][i])

代表问题：TSP、哈密顿路径、任务分配。

四、DP 的常见优化技巧

1. 空间优化：滚动数组

如果 dp[i] 只依赖于 dp[i-1]，可以用两个一维数组交替使用，或者直接用一维数组（注意遍历顺序）。

例：0-1 背包的一维优化。

2. 时间优化：单调队列/单调栈

在某些 DP 转移中，如果需要在一个滑动窗口内求最值，可以用单调队列优化到 O(1)。

例：滑动窗口最大值、多重背包的单调队列优化。

3. 时间优化：数据结构辅助

使用线段树、树状数组、平衡树等数据结构来加速状态转移中的查询和更新操作。

例：LIS 的 O(n log n) 解法（贪心+二分查找）。

4. 记忆化搜索

对于某些 DP 问题，可以用递归+记忆化（自顶向下）的方式实现，代码更直观。

例：斐波那契数列、背包问题的记忆化搜索版本。

五、学习 DP 的建议

1. 从经典问题入手

不要一开始就挑战难题。先把经典的 DP 问题（如背包、LIS、LCS）做透，理解其状态定义和转移方程。

2. 多画图、多模拟

DP 表的填充过程是理解算法的关键。手动模拟几个小案例，画出 DP 表，能帮助你建立直觉。

3. 总结模板，举一反三

每做完一道题，总结其状态定义、转移方程和代码模板。遇到新题时，先尝试套用已知的模板。

4. 从暴力递归到 DP

如果一个问题你能写出暴力递归解法，那么你就能将其改写为 DP（通过记忆化或自底向上）。这是一个很好的思维训练。

5. 刷题，刷题，刷题

DP 是一个需要大量练习的领域。LeetCode、洛谷、Codeforces 上有大量的 DP 题目。建议按分类刷题，逐个击破。

六、DP 系列回顾

在本系列的六篇文章中，我们系统地学习了：

文章	核心内容	代表问题
Part 5.1	DP 入门：背包问题	0-1 背包
Part 5.2	最长上升子序列 (LIS)	LIS 的 O(n²) 和 O(n log n) 解法
Part 5.3	最长公共子序列 (LCS)	二维 DP、路径回溯
Part 5.4	区间 DP	石子合并、按区间长度遍历
Part 5.5	树形 DP	树的最大独立集、DFS 后序遍历
Part 5.6	状态压缩 DP	TSP、位运算表示集合