专题进阶 · 动态规划推荐总顺序 · 第 73 / 148 课

给节点设置选与不选两个状态,以后序合并互不干扰的子树。

先学会这些,再进入本课 后序遍历 一维 DP
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

树形 DPTree DP

以后序顺序汇总孩子状态,必要时增加是否选择当前节点的维度。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

给节点设置选与不选两个状态,以后序合并互不干扰的子树。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

树上每个节点有收益,相邻节点不能同时选择,求最大总收益。线性房屋问题变成树后还怎么推?

02一步步得到方法

父节点选择会限制孩子

定义 take[u] 为必须选 u 时子树最优值,skip[u] 为不选 u 时子树最优值。选 u 后孩子不能选,所以 take[u]=value[u]+Σskip[v]。不选 u 时孩子可选可不选,所以 skip[u]=Σmax(take[v],skip[v])。

为什么可以直接把孩子结果相加?树中不同子树之间没有边,给定 u 的选择后,它们独立。一般图里不同分支可能有交叉约束,不能沿同一公式直接相加。

后序保证依赖先完成

先递归所有孩子,取得两个状态,再合成父节点。无向树的邻接表还含父边,要传入 parent 避免回走。代码要求输入确实是一棵树;有环时仅跳父节点不够。

收益允许负数且允许空选择,skip 可为 0,最终取根两状态最大值。若强制至少选一个节点,则要补充状态,避免空选择被误认作合法最优。

状态需要向父节点传递哪些约束

父节点通常不需要知道孩子整个子树的每个选择,只需要知道与父选择相关的几种最优结果。独立集问题用选根与不选根两个状态,正是因为父子不能同时选。

选当前节点时每个孩子只能取不选状态;不选当前节点时,孩子可各取较优状态。子树之间没有额外边,所以这些最优结果可以独立相加;一般图中该独立性可能被环破坏。

03把一个小例子完全算清楚

根 0 收益 5,孩子 1、2 收益 4、3;节点 1 的孩子 3 收益 6。

步骤计算与状态为什么这样做
叶子 3、2状态 (6,0)、(3,0)顺序为选、不选
节点 1take=4,skip=6不选 1 可选 3
根 0take=5+6+0=11;skip=6+3=9最优选 0、3

窄屏可左右滑动表格,阅读完整计算与理由。

答案 11,选择根不意味着跳过整个孩子子树,只禁止孩子节点本身。

04为什么这个方法成立

  1. 叶子状态正确。
  2. 固定 u 是否选择后,各子树约束独立,且孩子允许状态明确。
  3. 将各子树的最优合法状态相加,后序归纳得到整树最优。

05把推导翻译成代码

Python · 可独立运行的教学实现

def tree_independent_set(values, edges):
    n = len(values)
    if n == 0:
        return 0
    adj = [[] for _ in range(n)]
    for u,v in edges:
        adj[u].append(v); adj[v].append(u)
    def visit(u,parent):
        take,skip = values[u],0
        for v in adj[u]:
            if v == parent:
                continue
            child_take,child_skip = visit(v,u)
            take += child_skip
            skip += max(child_take,child_skip)
        return take,skip
    return max(visit(0,-1))

逐个理解关键决定

take += child_skip
选父只能要求孩子不选,仍可选孙子。
skip += max(child_take,child_skip)
不同孩子独立选择各自较优状态。

06时间、空间与实现范围

合法 n 节点树,每条边处理常数次,时间 O(n),邻接表 O(n),递归栈 O(h)。

链状大树可能触发 Python 递归深度限制,可改成显式后序;此实现不接受一般有环图或不连通森林。

07改变条件,检查哪里会出错

不选孩子就丢掉整棵孩子子树

skip[v] 仍可能包含孙子等节点的收益。

对有环图直接使用树形相加

子问题可能共享节点或相互约束,简单累加会重复计数或忽略跨边限制。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

星形树根 5、三个叶子各 3,选谁?

需要一点提示

比较 take 与 skip。

查看解析与答案

不选根,选三叶,收益 9。

练习 2 · 边界与辨析

一条链会退化为哪种问题?

需要一点提示

相邻不能同时选。

查看解析与答案

一维最大不相邻和,树形状态是它的自然推广。

练习 3 · 变式与迁移

一般图为何不能直接用 DFS 树求?

需要一点提示

DFS 树外仍有边。

查看解析与答案

跨子树边可能连接两个同时被选节点,破坏独立性,必须考虑额外约束。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。