树形 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(孩子两态)）；孩子先算完父亲才能算 → 按后序填表

树形 DP 三要素

状态挂节点：dp[u][...] 描述「以 u 为根的子树」的最优解。
子树即子问题：树的递归结构就是 DP 的无后效性来源。
后序即拓扑：孩子先于父亲就绪，一趟 DFS O(n) 填完。
同款：没有上司的舞会（带权独立集）、二叉树直径、树的重心。

再往上走是树上背包（每棵子树当一组物品做分组背包）与换根 DP（第二趟 DFS 把「以每个点为根」的答案摊到 O(n)）。至此 DP 大类九页、四种状态设计集齐：序列前缀（LIS）、区间（石子合并）、集合（TSP）、树（本页）。