Skip to content

电路布线

约 162 字小于 1 分钟

2024-11-03

思路

求最大不相交子集

二维数组 size 表示用于记录动态规划的表

初始化第一个节点,大于 c[0] 的设为 1,表示存在一个不相交子集

嵌套循环

  • i:表示考虑到第几个节点,即上方节点 [2, n)
    • j:表示取第几个点的不相交子集数,即下方节点 [1, n]
      • 若 j > c[i]I 表示该点可取, 需要比较去该点和不取该点哪个是最优解
      • 若 j < c[i]I 表示不可取, 则不相交子集数与上一点一致