引言 (Introduction)
前四篇文章完成了从一维 DP、二维 DP、背包问题到字符串 DP 的系统覆盖。本篇是本系列的收官之作，将聚焦于三种进阶 DP 技巧：状态压缩（将一整个维度编码为一个整数）、树形 DP（在递归的树结构上做 DP）、以及 DP 与其他思想的交叉应用。
本文是本系列第五篇，将覆盖三道综合性题目（打家劫舍 III、单词拆分、乘积最大子数组），并在结尾给出全系列的知识复盘对照表。
1. 树形 DP：LeetCode 337 打家劫舍 III
题目：小偷在二叉树结构的房屋中偷窃，不能偷直接相连的两个节点（父子关系），求最大收益。
1.1 从一维状态机到树
回顾 198 打家劫舍（一维数组）的状态定义：$dp[i][0/1]$ 表示不偷/偷第 $i$ 家。在树上，将 $i$ 替换为节点即可。每个节点的最优解由其左右子树的最优解构成——这满足最优子结构。
1.2 完整代码
from typing import Optional, Tuple
class TreeNode:
def __init__(self, val: int = 0, left: Optional['TreeNode'] = None,
right: Optional['TreeNode'] = None):
self.val = val
self.left = left
self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:
"""
返回 (不偷 node 的最大收益, 偷 node 的最大收益)
"""
if node is None:
return (0, 0)
left_not, left_rob = dfs(node.left)
right_not, right_rob = dfs(node.right)
# 不偷当前节点：左右可偷可不偷，分别取最大
not_rob = max(left_not, left_rob) + max(right_not, right_rob)
# 偷当前节点：左右都不能偷
rob = node.val + left_not + right_not
return (not_rob, rob)
return max(dfs(root))
复杂度：时间 $O(n)$（每个节点访问一次），空间 $O(h)$（递归栈深度）。
1.3 树形 DP 的模式
树形 DP 的核心特征是后序遍历：先递归处理左右子树，拿到子问题的答案，再组合出当前节点的答案。这与分治算法同构，区别在于子问题答案被显式地用状态变量表示。
树形 DP 的通用模板：
def dfs(node) -> State:
if node is None: return base_case
left_state = dfs(node.left)
right_state = dfs(node.right)
return combine(left_state, right_state, node.val)
常见的树形 DP 问题还包括：二叉树中的最大路径和（LeetCode 124）、二叉树的直径（543）、监控二叉树（968）。
2. LeetCode 139：单词拆分
题目：给定字符串 s 和单词字典 wordDict，判断 s 是否可以被拆分为字典中单词的组合（单词可重复使用）。
2.1 DP 状态定义
$dp[i]$：s 的前 $i$ 个字符是否可以被拆分。
即找到一个分割点 $j$，使得前 $j$ 个字符可拆分，且 $s[j:i]$ 是一个字典单词。
2.2 完整代码
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict)
n = len(s)
dp: List[bool] = [False] * (n + 1)
dp[0] = True # 空前缀始终可拆分
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # 找到一个就够
return dp[n]
复杂度：时间 $O(n^2)$（内层枚举 $j$ 和字符串切片），空间 $O(n + |dict|)$。
2.3 单词拆分与背包的联系
这本质上是「完全背包 + 计数问题」的变体：每个字典单词是一件物品（可无限用），目标是恰好拼出长度为 $n$ 的目标串。只不过这里的「容量」变成了字符串的位置，而非数值。这个映射说明了 DP 建模的高度抽象性——同一个 DP 框架适用于数值和字符串。
2.4 BFS 视角
单词拆分也可以用 BFS 求解：每个位置是一个节点，每个单词是一条有向边。DP 的填表顺序（$i$ 从 $1$ 到 $n$）恰好等价于 BFS 的层序遍历。两种解法的时间复杂度等价，但 DP 更简洁。
3. LeetCode 152：乘积最大子数组
题目：给定整数数组 nums（可能含负数），求乘积最大的连续子数组。
3.1 为什么普通的 Kadane 不能直接用于乘积？
在 53 最大子数组和中，$dp[i] = \max(nums[i], dp[i-1] + nums[i])$。但乘积不满足这个简单的递推——因为负数乘负数变成正数，当前最小的负数乘积可能在下一步变成最大正数乘积。
这就是本题的核心挑战：需要同时维护最大值和最小值两个状态。
3.2 状态定义与转移
$max\_dp[i]$：以 $i$ 结尾的最大乘积。 $min\_dp[i]$：以 $i$ 结尾的最小乘积。
转移：
$$max\_dp[i] = \max(nums[i],\ nums[i] \cdot max\_dp[i-1],\ nums[i] \cdot min\_dp[i-1])$$$$min\_dp[i] = \min(nums[i],\ nums[i] \cdot max\_dp[i-1],\ nums[i] \cdot min\_dp[i-1])$$3.3 完整代码
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
cur_max = cur_min = nums[0]
ans = nums[0]
for i in range(1, len(nums)):
candidates = (nums[i], nums[i] * cur_max, nums[i] * cur_min)
cur_max = max(candidates)
cur_min = min(candidates)
ans = max(ans, cur_max)
return ans
复杂度：时间 $O(n)$，空间 $O(1)$。
关键洞察：负数反转符号的性质迫使我们在 DP 状态中记录「看起来最差」的最小值。这是 DP 建模中的一个重要原则：当转移中存在符号反转、取反或互补关系时，需要同时维护互为镜像的多个状态。
4. 状态压缩 DP：以位运算代替维度
4.1 核心思想
当 DP 的一个维度只涉及「选/不选」的二进制决策时，可以用一个整数的二进制位来表示整个维度的状态。$dp[mask]$ 中 $mask$ 的每一位表示某个元素是否被选中。
常见应用：旅行商问题（TSP）、集合覆盖、分配问题（如 LeetCode 698 划分为 k 个相等的子集）。
4.2 典型模板
from typing import List
def tsp(dist: List[List[int]]) -> int:
"""旅行商问题：访问所有城市恰好一次的最短路径"""
n = len(dist)
INF = float('inf')
# dp[mask][i]: 已访问城市集合为 mask，当前在城市 i 的最短路径
dp: List[List[float]] = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # 从城市 0 出发
for mask in range(1 << n):
for i in range(n):
if dp[mask][i] == INF:
continue
for j in range(n):
if mask & (1 << j): # j 已访问，跳过
continue
new_mask = mask | (1 << j)
dp[new_mask][j] = min(dp[new_mask][j],
dp[mask][i] + dist[i][j])
# 回到起点
full_mask = (1 << n) - 1
return int(min(dp[full_mask][i] + dist[i][0] for i in range(n)))
状态压缩 DP 的时间复杂度通常带指数因子（$O(n^2 \cdot 2^n)$），只适用于 $n \le 20$ 左右的场景。但它将指数级暴力搜索优化为有记忆的 DP，这是 DP 在 NP-hard 问题上获得可行近似解的关键技术。
5. 全系列复盘对照表
本系列共五篇文章，覆盖了 18 道 LeetCode 题目和 3 个经典算法，以下是完整的知识地图：
| 篇目 | 主题 | 核心概念 | LeetCode 题目 | 关键技巧 | 典型复杂度 |
|---|---|---|---|---|---|
| 第一篇 | 核心概念与一维 DP | 最优子结构、重叠子问题、记忆化 vs 递推 | 53 最大子数组和198 打家劫舍213 打家劫舍 II | 状态定义、滚动变量状态机建模环形破环为线 | $O(n)$ |
| 第二篇 | 二维 DP 与网格 | 二维状态表格、填表顺序 | 62 不同路径64 最小路径和221 最大正方形 | 滚动数组、哨兵列DP 表反推路径prev 保存左上角 |
$O(mn)$、$O(n)$ 空间 |
| 第三篇 | 背包问题族 | 0/1 背包、完全背包、组合 vs 排列 | 416 分割等和子集322 零钱兑换518 零钱兑换 II | 倒序保证 0/1正序允许无限循环顺序决定组合/排列 | $O(nW)$、$O(W)$ 空间 |
| 第四篇 | 子序列与字符串 DP | 双串 DP、区间 DP | 1143 LCS300 LIS72 编辑距离5 最长回文子串 | 双串表格对齐二分优化 DP按长度填区间的套路 | $O(mn)$ / $O(n \log n)$ |
| 第五篇 | 进阶技巧 | 树形 DP、状态压缩、多状态维护 | 337 打家劫舍 III139 单词拆分152 乘积最大子数组 | 后序递归 DP符号反转的多状态维护字符位置的背包映射 | $O(n)$ / $O(n^2)$ |
全系列方法论总结
-
状态定义是 DP 的灵魂：同一个问题可能有多种状态定义，好的定义让转移方程简洁，差的定义让代码复杂数倍。多做题、多比较不同定义的差异。
-
填表顺序决定正确性：背包的倒序/正序、区间的按长度填表、树形 DP 的后序遍历——这些都是不可随意改变的硬约束。
-
空间优化是进阶标志：从二维到一维（滚动数组）、从一维到常数（滚动变量）、从数组到整数（状态压缩），每一步都要求精确理解状态依赖关系。
-
DP 不是孤立的算法：LIS 的二分优化、单词拆分的 BFS 等价视角、Dijkstra 中的 DP 思想——这些联系提醒我们，算法设计的边界是模糊的，真正的高手能在方法论之间自由切换。
-
证明比直觉更可靠：DP 的正确性来自最优子结构和无后效性。面对一道新题，先验证这两个前提，再动手写状态转移方程。
结论 (Conclusion)
五篇文章走下来，我们从 DP 的理论基石出发，经历了一维、二维、背包、字符串、树形、状态压缩等层层推进的建模训练。DP 的学习曲线是先陡后缓的——前两篇需要克服「状态定义恐惧症」，而一旦掌握了建模范式，后续的应用就会越来越快。
DP 学习的终点不是「能做几道题」，而是面对一个陌生问题，能自主完成从状态定义到转移方程到空间优化的全流程建模。这需要大量练习，但方向已经清晰。
与贪心系列的互补阅读：DP 和贪心共享最优子结构这一前提，但 DP 舍弃了贪心选择性质以换取更广的适用范围。当你面临一个优化问题时，先问「能贪心吗」，不能则走向 DP，再不能则考虑回溯 + 剪枝或转化为图论问题。这构成了算法设计中最核心的策略选择框架。
下一篇建议：如果你已经完成了贪心和 DP 两个系列，图论算法（BFS/DFS 的系统化、最短路径、拓扑排序、并查集）将是自然的下一个学习板块。