来自 p_b_p_b。
设 \(out(u)\) 为 \(u\) 的临域点集，\(f_S\) 表示点集为 \(S\) 时的最大点独立集。
转移考虑拿出最大的那个点 \(u\)，枚举其选不选则有 \(f_S = \max(f_{S-u}, f_{S-u-out(u)}+1)\)。
当 \(S\) 只有后 \(\frac{n}{2}\) 个点时记忆化，时空复杂度都是 \(\mathcal{O}(2^{\frac{n}{2}})\)，因为考虑分治树，前 \(\frac{n}{2}\) 层只有 \(\mathcal{O}(\frac{n}{2})\) 个节点，后 \(\frac{n}{2}\) 层记忆化后只有 \(\mathcal{O}(\frac{n}{2})\) 个状态。
可以带权，可以计数，可以限制独立集大小的范围。当 \(S\) 不联通时可以分开计算，跑的飞快。
标签：frac,最大,独立,点集,mathcal,做法,比较,out From： https://www.cnblogs.com/Aria-Math/p/18072539