这是一道标准的树形动态规划题目,我们能从题目得到以下信息:
1. 各个子节点的权值(废话)
2. 本题的数据结构——树(核心)
简化一下:假如本题只有三个节点:总经理(23)——员工A(10)、B(15),那么有两种方案:
1. 邀请父节点,不要子节点,得到的权值为23
2. 邀请两个子节点,得到权值25
但是这个时候问题又来了,我们能直接丢一个max上去吗?不行。你可以试试
所以本体的核心是一个二维数组dp,一边表示该节点“参加”这一状态,另一边相反。
使用 DFS(深度搜索)算法由叶节点最优值向上更新至父节点的最优值。
更新(状态)值存储在二维状态(dp)数组中。
dfs核心代码
完整代码
如果你觉得有帮助,点个赞吧