动态规划
01 / 共享的机制
一张表格逐格填充自己 —— 每一格都由 常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。
02 / 一句话本质
运行后序 DFS —— 先处理子节点，再处理父节点。 每个节点返回一个值对： 偷取本节点时的最大收益，以及跳过本节点时的最大收益。
题目不偷相邻节点的最大金额树[3, 4, 5, 1, 3, -, 1]
二叉树上的后序 DP —— 每个节点在两棵子树都返回各自的 rob / skip 对之后再求解。
步
0 / 7
节点
—
rob
—
skip
—
答案
—
0 / 7
03 / 模式骨架
# 树形 DP —— 后序，每个节点返回 (rob, skip)function dp(node):if node is null: return (0, 0)(lr, ls) ← dp(node.left) # 先递归左子树(rr, rs) ← dp(node.right) # 再递归右子树rob ← node.val + ls + rs # 偷本节点，跳过两个子节点skip ← max(lr, ls) + max(rr, rs) # 每个子节点取最优return (rob, skip)lr, ls ← dp(root)answer ← max(lr, ls)
04 / 什么时候用这个模式
"必须使用后序"
父节点在两个子节点都求解完毕之前无法做决策。前序或中序会迫使你猜测子节点的值。 后序是自底向上计算的自然遍历顺序。
"返回对而非单值"
每个节点返回单个标量是不够的 —— 父节点需要知道两种结果（偷和不偷），才能做出自己的决策。返回一个值对是子树与父节点之间的最简接口。
"空节点基线为 (0, 0)"
空子节点对 rob 和 skip 的贡献都是 0。这使递推式保持统一 —— 无需在循环体中对叶子节点或只有单个子节点的节点做特殊处理。基线值能干净地向上传播。
"可推广到 rob/skip 之外"
任何节点的最优值依赖其子节点最优值的问题都遵循这一结构：后序 DFS、返回固定长度的元组、在父节点处合并。 直径（经过根的最长路径 vs. 不经过）、最大路径和、监控摄像头，都是同一骨架的变体。
05 / 常见坑
用哈希表或全局记忆化替代返回值。
常见错误：定义
dp 为从节点到值的哈希表，再用自顶向下的递归加记忆化来填充。 这样做确实可行，但隐藏了自底向上的结构。返回值方法更简洁 —— 它让数据流一目了然，且只使用 O(H) 的栈空间， 而非 O(N) 的记忆化空间。只返回最终答案，而非完整的值对。
如果你写
dp(node) = max(rob, skip) 只返回单个数，父节点就无法区分两种情况， 会导致错误的状态转移 —— 例如误认为子节点的结果总是"跳过"，从而多算收益。 务必一直返回完整的值对，直到根节点为止。混淆合并子节点时应使用哪个值。
rob(node) = val + skip(left) + skip(right) —— 加的是子节点的 skip 值，而非 rob 值，因为偷父节点意味着禁止偷子节点。skip(node) = max(rob(L), skip(L)) + max(rob(R), skip(R)) —— 每个子节点独立选择最优。将这两条递推式互换是常见错误，会导致答案错误。06 / 去 LeetCode 上练习
中等16
01Unique Binary Search Trees II— LC 95→02Unique Binary Search Trees— LC 96→03House Robber III— LC 337→04Path Sum III— LC 437→05Longest Univalue Path— LC 687→06All Possible Full Binary Trees— LC 894→07Distribute Coins in Binary Tree— LC 979→08Smallest String Starting From Leaf— LC 988→09Tree Diameter— LC 1245→10Maximum Product of Splitted Binary Tree— LC 1339→11Longest ZigZag Path in a Binary Tree— LC 1372→12Count Good Nodes in Binary Tree— LC 1448→13Diameter of N-Ary Tree— LC 1522→14Number of Good Leaf Nodes Pairs— LC 1530→15Most Profitable Path in a Tree— LC 2467→16Minimum Score of a Path Between Two Cities— LC 2492→
困难7
01Binary Tree Maximum Path Sum— LC 124→02Sum of Distances in Tree— LC 834→03Binary Tree Cameras— LC 968→04Number of Ways to Reorder Array to Get Same BST— LC 1569→05Longest Path With Different Adjacent Characters— LC 2246→06Difference Between Maximum and Minimum Price Sum— LC 2538→07Count Number of Possible Root Nodes— LC 2581→
— / 什么时候用哪个
一维线性
当下标 i 处的答案只依赖常数个更早的下标时使用。
打家劫舍 · 爬楼梯 · 最大子段和
二维网格
当状态由两个下标组成 —— 网格,或两条相互作用的序列。
最短路径 · LCS · 编辑距离
背包
当每个物品都触发一次选 / 不选决策、且有容量约束时使用。
子集和 · 找零 · 划分
区间
当状态是一个区间
(i, j)、答案由内部区间组合得出时使用。回文 · 矩阵链 · 戳气球
状态机
当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。
股票 · 冷冻期 · 双状态
树形 DP
当问题定义在树上、且每个节点的答案依赖其子节点答案时使用。
打家劫舍 III · 二叉树直径 · 最大路径和
位掩码
当状态是子集(通常
N ≤ 20),且只关心选了哪些、不关心顺序时使用。分配 · TSP · 最小覆盖团队