[!info] related notes 动态规划 二叉树基础 打家劫舍 III

树形 DP

一句话

在树的每个节点上维护若干状态，通过 DFS 自底向上把子树答案合并到父节点。

识别信号

• 题目对象是树 / 二叉树
• 当前节点的答案依赖孩子节点的答案
• 常见问法：选 / 不选当前节点，子树最大值，路径和，染色，覆盖

典型状态设计

1. 当前节点选 / 不选

例如 [[house-robber-iii|打家劫舍 III]]：

• f[node][0]：不选当前节点
• f[node][1]：选当前节点

2. 返回多个量

DFS 返回一个数组 / 对象：

• 当前子树最大值
• 当前节点向上提供的信息

通用模板

function dfs(node) {
    if (!node) return ...;

    const left = dfs(node.left);
    const right = dfs(node.right);

    const state0 = ...left...right;
    const state1 = ...left...right;

    return [state0, state1];
}

高频坑

• 把“当前节点状态”和“整棵树最终答案”混了
• 忘了空节点的返回值
• 没想清楚父子之间是否有互斥关系

入门题

• 打家劫舍 III