首页 > 其他 > 详细

动态规划进阶

时间:2020-07-21 22:46:23      阅读:83      评论:0      收藏:0      [点我收藏+]

第一类 · 树形动态规划

问题一:求树上最大权独立集

题意描述

  有一棵大小为 $n$ 的树,其中有 $n-1$ 组点有连边,请找到大小最大的一个集合,使得树中以编号为集合内元素的节点两两无直接连边。

  $n \le 5000$。

  (简单讲,就是从一棵树内找到尽可能多的点,并且这些点两两没有连边)

算法一(非通过算法)

  我们可以枚举每一个点选或不选,选完了判断是否成立。时间复杂度为 $O(2^n)$,肯定会超时。

动态规划进阶

原文:https://www.cnblogs.com/zengpeichen/p/13357045.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!