电路布线
约 162 字小于 1 分钟
2024-11-03
思路
求最大不相交子集
二维数组 size 表示用于记录动态规划的表
初始化第一个节点,大于 c[0] 的设为 1,表示存在一个不相交子集
嵌套循环
- i:表示考虑到第几个节点,即上方节点 [2, n)
- j:表示取第几个点的不相交子集数,即下方节点 [1, n]
- 若 j > c[i]I 表示该点可取, 需要比较去该点和不取该点哪个是最优解
- 若 j < c[i]I 表示不可取, 则不相交子集数与上一点一致
- j:表示取第几个点的不相交子集数,即下方节点 [1, n]