树形 DP（打家劫舍 III）
动态规划 · 状态挂节点 · 后序即拓扑
小偷上树了
房子连成一棵二叉树，直接相连的父子不能同偷，求最大金额。本页的树（层序 [4, 1, 5, 3, 6]）：
4 ← 根
/ \
1 5
/ \
3 6线性打家劫舍在数组上「偷不偷第 i 家」；上了树，链变成了分叉——但 DP 的骨架不变：每个节点两个状态。
两态与后序
选它：孩子都不能选 → 值 + Σ 孩子的「不选」；不选它：孩子自由发挥 → Σ max(孩子两态)。算父亲前孩子必须先算完——后序遍历天然就是拓扑序。下表每行一个节点、两列两态：注意填表跳着走（LL → LR → L → R → 根），那正是后序的足迹；黄格是引用的孩子状态。右侧代码随每一步同步高亮。
| 选 | 不选 | |
|---|---|---|
| 根 4 | ||
| L 1 | ||
| R 5 | ||
| LL 3 | ||
| LR 6 |
二叉树上打家劫舍：父子不能同偷，求最大金额。树：根 4，左子 1（孩子 3、6）、右子 5。每个节点两个状态——选（值 + Σ孩子的不选）/ 不选（Σ max(孩子两态)）；孩子先算完父亲才能算 → 按后序填表
1function rob(root: Node | null): number {
2 const dfs = (nd: Node | null): [number, number] => {
3 if (!nd) return [0, 0]; // 空子树两态皆 0
4 const [ls, ln] = dfs(nd.left); // 后序：先算孩子
5 const [rs, rn] = dfs(nd.right);
6 const sel = nd.val + ln + rn; // 选它：孩子都不能选
7 const not = Math.max(ls, ln) + Math.max(rs, rn); // 不选：孩子自由
8 return [sel, not];
9 };
10 return Math.max(...dfs(root)); // 根取两态最大
11}
树（层序）[4, 1, 5, 3, 6]
后序LL → LR → L → R → 根
1 / 10
树形 DP 三要素
状态挂节点：dp[u][...] 描述「以 u 为根的子树」的最优解。
子树即子问题：树的递归结构就是 DP 的无后效性来源。
后序即拓扑：孩子先于父亲就绪，一趟 DFS O(n) 填完。
同款：没有上司的舞会（带权独立集）、二叉树直径、树的重心。
子树即子问题：树的递归结构就是 DP 的无后效性来源。
后序即拓扑：孩子先于父亲就绪，一趟 DFS O(n) 填完。
同款：没有上司的舞会（带权独立集）、二叉树直径、树的重心。
再往上走是树上背包（每棵子树当一组物品做分组背包）与换根 DP（第二趟 DFS 把「以每个点为根」的答案摊到 O(n)）。至此 DP 大类九页、四种状态设计集齐：序列前缀（LIS）、区间（石子合并）、集合（TSP）、树（本页）。