算法动态规划

树形DP

字数统计: 1.7k字   |   阅读时长: 6分
, ,

摘要: 树形DP的思想与经典问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

树形DP思想

在树形结构上求解问题，每个节点都可以视为一棵子树，在某棵以 u 为根的树上的答案为 dp[u]，其重复子问题是子树上的问题，对应的答案为 dp[v]。状态转移方向就是从子节点到父节点，当前以 u 为根的树拿到各个以 v 为根的子树的答案后进行整合，形成当前树的答案，然后继续向上传。状态转移方程大致是下面这样的形式：

1
2
3
4
dp[u][s] = 常数                    u为叶子节点
         = f(dp[v1], dp[v2], ...)  v1,v2,...为u的子节点
s 为与 u 相关的状态
答案 g(dp[root])

以求树高为例，转移方程如下：

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[u] := 子树 u 的高度

答案：
dp[root]

初始化：
dp[u] = 1; u 为叶节点

状态转移：
dp[u] = max(dp[v] + 1); v 为 u 的子节点。

有时候子树的答案交给当前根之后就不会再用到了，这种情况有点像后序遍历处理的问题，此时一般就用后序遍历而不提树形DP的事，例如 树的高度 以及 树的DFS遍历 中后序遍历部分的问题。

阶段和附加状态

从阶段和附加状态的角度看，树形 DP 一般以深度作为阶段，状态表示的第一维是节点编号，隐含了阶段信息，例如前面的树高问题的 $dp[u]$。

状态计算顺序

树形 DP 的阶段以遍历序的方式进行推导。根据情况选择自底向上或自顶向下实现。

  • 自顶向下：记忆化搜索
  • 自底向上：拓扑序

dpup 和 dpdown

在有的问题中，树形 DP 状态设计要分为 dpup 和 dpdown 并且转移的时候分成两步 dfs 来做(有时通过一些推导也可以变成一趟dfs)，称为二次扫描与换根法。参考文章 二次扫描与换根DP。

树形DP解决的经典问题

1. 树的高度

本题直接后序遍历即可。

2. 树的最长链

本题相关的内容参考文章 【树形DP】树的直径。

3. 某点到所有点的最大距离最小

本题相关的内容参考文章 二次扫描与换根DP。

4. 同色最长链

与普通最长链的区别是取 $v \in son[u]$ 时，取同色的 $v$。

5. 树的重心

树的重心定义：最大子树最小。算法如下：

1
2
3
4
5
状态定义：
dp[u] = 以 u 为根的子树的最小

状态转移：
dp[u] = (max(dp[v]), n - dp[u]);  v 为 u 的子节点

6. 最大点独立集

最大点独立集定义：两两无边相邻。

此问题在一般图上很难做，在树上和二分图上可做，最简明的是在树上做。

不能简单地将树分层。算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[u][0] := u 不选的最大点独立集
dp[u][1] := u 选的最大点独立集

状态转移：
dp[u][0] = 0   u 为叶子节点
         = sum(max(dp[v][0], dp[v][1]))   v 为 u 的子节点

dp[u][1] = 1   u 为叶子节点
         = sum(dp[v][0]) + 1     v 为 u 的子节点

答案：max(dp[root][0], dp[root][1])

7. 最小点覆盖集

最小点覆盖集定义：点集覆盖了所有的边，即对于 $G = (V, E)$ 中任意 $e=uv \in E$，$uv$ 中至少有一个在点集中。

算法如下：

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[u][0] := u 不选的最小点覆盖集
dp[u][1] := u 选的最小点覆盖集

状态转移：
dp[u][0] = 0  u 为叶子
         = sum(dp[v][1])  v 为 u 的子节点
dp[u][1] = 1  u 为叶子
         = sum(min(dp[v][0], dp[v][1])) + 1

答案：min(dp[root][0], dp[root][1])

8. 最小点支配集

最小点支配集定义：所有的点，要么属于支配集，要么与支配集中的点相连。

比较复杂的地方：对于 u，有可能不属于支配集合，并且子节点也不属于支配集合，但是父节点属于支配集合。这种情况在转移的时候必须注意，dp状态，需要增加一维表示 u 的子节点是否属于支配集(u 是否被支配)。

算法如下：

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[u][0] := u 选了
dp[u][1] := u 未选，但是 u 被支配了(u 的子节点中有属于支配集的)
dp[u][2] := u 未选，且 u 未被支配

状态转移：
dp[u][0] = sum(min(dp[v][0], dp[v][1], dp[v][2])) + 1
dp[u][2] = sum(dp[v][1])
dp[u][1] := 至少有一个 son(u) 中的 v 被选了

答案： min(dp[root][0], dp[root][1])

dfs 在枚举 $v \in son(u)$ 过程中维护 tmp = sum(min(dp[v][0], dp[v][1]))，记一个 flag 表示是否有某个 v，$dp[v][0] \leq dp[v][1]$。

若 flag 被触发，则 dp[u][1] = tmp 即可，因为 tmp 记录的情况已经有 v 被选了。

若 flag 未触发，则对所有 v，均有 $dp[v][0] > dp[v][1]$，但是必须要选一个，就看哪个 v 的 $dp[v][0] - dp[v][1]$ 更小。

因此状态转移中 dp[u][1] 的转移方程如下：

1
2
dp[u][1] = tmp     f被触发
         = min(tmp - dp[v][1] + dp[v][0])   f未被触发

u 为叶子的边界条件：

1
2
3
dp[u][0] = 1
dp[u][1] = +INF
dp[u][2] = 0

力扣 968. 监控二叉树 是相关的一道题，题解参考文章 【树形DP】力扣968-监控二叉树。

9. 有依赖的背包

树形背包问题相关的内容参考文章 树形背包。

题目

本题相关的内容参考文章 二次扫描与换根DP。

本题相关的内容参考文章 拓扑排序的方案数。

本题相关的内容参考文章 力扣1617-计子树中城市之间最大距离。

Share