問(wèn)題描述：

在一塊電路板的上、下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線（i，π（i）） 將上端接線柱i與下端接線柱π（i）相連，如下圖。其中，π（i），1≤ i ≤n，是｛1，2，…，n｝的一個(gè)排列。導(dǎo)線（I， π（i））稱(chēng)為該電路板上的第i條連線。對(duì)于任何1 ≤ i ≤ j ≤n，第i條連線和第j條連線相交的充要條件是π（i）》 π（j）。

π（i）=｛8，7，4，2，5，1，9，3，10，6｝

在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets = ｛i，π（i），1 ≤ i ≤ n｝的最大的一個(gè)子集，這個(gè)子集中的導(dǎo)線互相不相交。

問(wèn)題分析：

顯然這是一個(gè)組合問(wèn)題，對(duì)于組合問(wèn)題中求最優(yōu)解的方法基本都是動(dòng)態(tài)規(guī)劃算法。現(xiàn)在表述一下如何劃分子問(wèn)題：

用B（i，j）表示最優(yōu)解，其中，i是上端接線柱的序號(hào)，j是下端接線柱的序號(hào)，B（i，j）表示序號(hào)小于或等于i的上端接線柱和序號(hào)小于或等于j的下端接線柱中不相交連線的最大集合。 用size（i，j）表示集合中導(dǎo)線的數(shù)目（size（i，j）=|B（i，j）|）。B（i，j）的值蘊(yùn)含在B（i-1，j）和B（i，j-1）這倆個(gè)子問(wèn)題中，對(duì)于有2xN個(gè)接線柱的電路板，那么B（N，N）就是其解了。

對(duì)于上端接線柱t，用 π（t）表示與他相連的下端接線柱

那么遞推公式為：

遞推公式證明：

對(duì)于從B（i-1，j）或B（i，j-1）到B（i，j）要么會(huì)多加一條導(dǎo)線，要么不加。

1. 當(dāng) j==π（i）時(shí)，（i，j）則是一條導(dǎo)線，且這條導(dǎo)線對(duì)B（i-1，j-1）的值沒(méi)有影響，因?yàn)锽（i-1，j-1）中的任意的一條導(dǎo)線的節(jié)點(diǎn)序號(hào)（無(wú)論是上端節(jié)點(diǎn)序號(hào)還是下端節(jié)點(diǎn)序號(hào)）都小于i，j，這由其空間位置決定的。

現(xiàn)在求B（i，j）， 即求序號(hào)小于或等于i的上端接線柱和序號(hào)小于或等于j的下端接線柱中不相交導(dǎo)線的最大集合。顯然應(yīng)是B（i-1，j-1）U（i，j）。

2 。 當(dāng)j！= π（i）時(shí)。假如問(wèn)題是從B（i，j-1）到B（i，j），那么下端新加入的接線柱j要么與上端的1至i-1個(gè)接線柱構(gòu)成導(dǎo)線（與第i個(gè)接線柱構(gòu)成導(dǎo)線的情況在上面已經(jīng)討論），要么不構(gòu)成。

如果構(gòu)成的話那么這種情況其實(shí)已經(jīng)在B（i-1，j）中討論了，這里不再考慮。那么B（i，j） 應(yīng)是序號(hào)區(qū)間比他小一點(diǎn)的子問(wèn)題的解。小一點(diǎn)是多少，肯定就是少一個(gè)接線柱了，也就是B（i-1，j）。

如果不構(gòu)成的話，那么B（i，j）肯定就是序號(hào)區(qū)間比他小一點(diǎn)的子問(wèn)題的解了。

對(duì)于B（i，j）可能由B（i-1，j）或B（i，j-1）過(guò)渡而來(lái)，所以B（i，j）取其中較大的一個(gè)。