树形 DP

动态规划

说明

从子节点状态汇总父节点；下例求树的最大独立集权重。

分析

对每个树节点分别计算“选当前节点”和“不选当前节点”两种状态。选中时孩子都不能选；不选时每个孩子可独立取较优状态。后序递归保证孩子先算好，最后取根的两种状态较大值。

图解推演

正文根节点权重 5、两孩子权重 4 和 7。选根只能得 5；不选根可以同时选两个孩子，得 11。孩子之间没有边才使两个子问题独立；普通图若存在跨子树边，这个分解会失效。负权节点允许不选时，应保留价值 0 的空集合。

查看图表代码

适用前提与边界

示例假设输入是一棵树。

示例输入与调用

fmt.Println(TreeIndependentSet([][]int{{1, 2}, {0}, {0}}, []int{5, 4, 7}))

运行输出

11

完整 Go 示例

package main

import "fmt"

func TreeIndependentSet(g [][]int, weight []int) int {
	if len(g) == 0 {
		return 0
	}
	var dfs func(int, int) (int, int)
	dfs = func(v, parent int) (int, int) {
		skip, take := 0, weight[v]
		for _, w := range g[v] {
			if w == parent {
				continue
			}
			a, b := dfs(w, v)
			skip += max(a, b)
			take += a
		}
		return skip, take
	}
	a, b := dfs(0, -1)
	return max(a, b)
}

func main() {
	fmt.Println(TreeIndependentSet([][]int{{1, 2}, {0}, {0}}, []int{5, 4, 7}))
}