题意描述
有一棵大小为 $n$ 的树,其中有 $n-1$ 组点有连边,请找到大小最大的一个集合,使得树中以编号为集合内元素的节点两两无直接连边。
$n \le 5000$。
(简单讲,就是从一棵树内找到尽可能多的点,并且这些点两两没有连边)
算法一(非通过算法)
我们可以枚举每一个点选或不选,选完了判断是否成立。时间复杂度为 $O(2^n)$,肯定会超时。
动态规划进阶
原文:https://www.cnblogs.com/zengpeichen/p/13357045.html