动态规划电路布线 用动态规划法求解电路布线问题 为确定导线集Nets = {i,π(i),1 ≤ i ≤ n}的最大不想交子集,将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。现分析最优子结构性质。 记N(i,j) = {t|(t, π(i)) ∈ Nets,t ≤ i, π(t)