動態(tài)規(guī)劃的分類解析

動態(tài)規(guī)劃動態(tài)規(guī)劃什么是動態(tài)規(guī)劃動態(tài)規(guī)劃的條件動態(tài)規(guī)劃的關(guān)鍵幾種常見動態(tài)規(guī)劃的種類例題分析什么是動態(tài)規(guī)劃動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題但是經(jīng)分解得到的子問題往往不是相互獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了很多次。假如能夠保存已解決的子問題的答案，而在須要時再找出已求得的答案，就可以避開大量重復計算，從而得到多項式時間算法。

由此不難得出結(jié)論：動態(tài)規(guī)劃實質(zhì)就是記憶化搜尋下面這個數(shù)塔的例子將形象地向我們展示這樣的結(jié)論給你一個數(shù)字三角形,形式如下: 1 23 8518 142110 找出從第一層到最終一層的一條 路,使得所經(jīng)過的權(quán)值之和最小或 者最大.當然，大家都很清晰的知道轉(zhuǎn)移方程為opt[i][j]=max{opt[i-1][j],opt[i-1][j-1]}+a[i][j]，邊界條件特殊處理即可。但只要細致想想就會發(fā)覺，這不過是一個加了強力剪枝的記憶化搜尋而已，因為每個點我們只記錄到當前節(jié)點的最優(yōu)解，因此省去了大量的重復計數(shù)和明顯不是最優(yōu)解的狀況，從而使運行速度有了極大的優(yōu)化動態(tài)規(guī)劃的條件 而在求解的過程中一道能運用動規(guī)解決的題必需具備以下幾個條件無后效性,即某階段的狀態(tài)一旦確定，則此后過程的演化不再受此前各狀態(tài)及決策的影響。也就是說，“將來與過去無關(guān)”，當前的狀態(tài)是此前歷史的一個完整總結(jié)，此前的歷史只能通過當前的狀態(tài)去影響過程將來的演化。滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，即一個問題的最優(yōu)解必需是在子問題取得最優(yōu)解的狀況下決策出來的動態(tài)規(guī)劃的過程可以簡潔地描述為找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。依據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。動態(tài)規(guī)劃的關(guān)鍵有明確的狀態(tài)狀態(tài)轉(zhuǎn)移方程清晰正確幾種常見動規(guī)的種類線性動規(guī)背包問題區(qū)間動規(guī)樹形動規(guī)下面讓我們通過幾個例子來了解這些基本動規(guī)的思索方法攔截導彈（Noip2002）某國為了防衛(wèi)敵國的導彈攻擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達隨意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕獲到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截全部的導彈。輸入導彈依次飛來的高度，計算這套系統(tǒng)最多能攔截多少導彈。狀態(tài)的確定狀態(tài)的表示——f[i]，表示當?shù)趇個導彈必需攔截時，前i個導彈中最多能攔截多少。每個導彈有確定的高度，當前狀態(tài)就是以第i個導彈為最終一個攔截的導彈。以前狀態(tài)就是在這個導彈之前攔截的那個導彈。對于f[i]，我們考察在i之前位置的導彈，找到全部可以連接上的導彈k（即滿足其高度大于等于第i個導彈），選擇其中f[k]值最大的一個，f[i]=f[k]+1；假如沒有滿足條件的k，則f[i]=1。這是線性動態(tài)規(guī)劃的經(jīng)典例題。代碼for(inti=1;i<=n;i++) scanf("%d",&a[i]);for(inti=1;i<=n;i++){ intmx=1; for(intj=1;j<i;j++) if(a[j]>=a[i])mx=max(mx,f[j]+1); f[i]=mx;}intans=0;for(inti=1;i<=n;i++) ans=max(ans,f[i]);printf("%d\n",ans);最低通行費一個商人穿過一個N*N的正方形的網(wǎng)格，去參與一個特殊重要的商務活動。他要從網(wǎng)格的左上角進，右下角出。每穿越中間1個小方格，都要花費1個單位時間。商人必需在(2N-1)個單位時間穿越出去。而在經(jīng)過中間的每個小方格時，都須要繳納確定的費用。這個商人期望在規(guī)定時間內(nèi)用最少費用穿越出去。請問至少須要多少費用？留意：不能對角穿越各個小方格（即，只能向上下左右四個方向移動且不能離開網(wǎng)格）。最低通行費輸入第一行是一個整數(shù)，表示正方形的寬度N(1<=N<100)；后面N行，每行N個不大于100的整數(shù)，為網(wǎng)格上每個小方格的費用。輸出至少須要的費用。分析這個問題的關(guān)鍵在于發(fā)覺對移動方向的限制：即由于必需在(2N-1)單位時間內(nèi)完成移動，因此僅能向下或者向右移動。當移動方向限定后，不難看出這個問題就是變形的數(shù)塔問題，于是可以借助動態(tài)規(guī)劃高效解決。狀態(tài)的確定我們用opt[i][j]表示從左上角入口移動到第i行j列的最小代價。則opt[i,j]=min{opt[i-1][j],opt[i][j-1])+a[i][j];最終輸出opt[n][n];代碼for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf(“%d”,&a[i][j]);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];printf(“%d\n”,f[n][n]);乘積最大國際數(shù)學聯(lián)盟確定的“2000—世界數(shù)學年”，又恰逢我國著名數(shù)學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學智力競賽活動，你的好摯友XZ也有幸得以參與。活動中，主持人給全部參與活動的選手出了這樣一道題目：設有一個長度為N(N≤40)的數(shù)字串，要求選手運用M(M≤6)個乘號將它分成M+1個部分，找出一種分法，使得這M+1個部分的乘積最大。同時，為了幫助選手能夠理解題意，主持人還舉了如下一個例子：有一個數(shù)字串：312，當N=3，M=1時會有兩種分法：⑴3×12=36⑵31×2=62這時，符合題目要求的結(jié)果是：31×2=62?，F(xiàn)在，請你幫助你的好摯友XZ設計一個程序，求得正確的答案。分析由于自然數(shù)位數(shù)的上限為40，乘號數(shù)的上限為6，因此最大乘積位數(shù)的上限接近42位。明顯，運算任何整數(shù)類型都無法容納如此之大的數(shù)據(jù)，只能接受高精度運算，限于篇幅，對于高精度的加法運算、乘法運算和比較大小的運算，這里不作介紹，只是對的乘號最佳插入方式進行探討：假設s1‥si(2≤i≤n)中插入j個乘號，其中s1‥sk中插入了j-1個乘號，即乘式中的第j+1項為sk+1‥si(j≤k≤i-1)：分析設ans[i][j]——長度為i的數(shù)串中插入j個乘號的最大乘積（整型數(shù)組）。明顯ans[i][0]=s1..si對應的整型數(shù)組；ans[i][j]=max{ans[k][j-1]×sk+1..si}（1≤i≤n，1≤j≤min{i-1,m}，j≤k≤i-1）ans[n][m]即為其解。分析由于乘式中第j+1項sk+1‥si為常量，因此要使得ans[i][j]最大，則s1‥sk中插入j-1個乘號的乘積必需最大；同樣，為了找尋第j個乘號的最佳插入位置，必需一一查閱子問題ans[j][j-1]‥ans[i-1][j-1]的解。明顯該問題具備無后效性、最優(yōu)子結(jié)構(gòu)的特征，適用于動態(tài)規(guī)劃方法。狀態(tài)的確定我們用ans[i][j]表示前i個字符插入j個乘號可以獲得的最大值則有：ans[i][0]=s1..sians[i][j]=max{ans[k][j-1]×sk+1..si}(j≤k≤i-1)ans[n][m]即為其解。代碼輸入n，m和數(shù)串s；fori←1tondoans[i][0]←s1..si對應的整數(shù)數(shù)組；fori←2tondo

{階段：枚舉數(shù)串的長度}forj←1tomin{i-1,m}do

{狀態(tài)：枚舉長度為i的數(shù)串中插入的乘號個數(shù)}fork←jtoi-1do{決策：枚舉第j個乘號的插入位置}beginnext←sk+1..si對應的整數(shù)數(shù)組；

{計算第j+1項}ans[i][j]←max{ans[i][j]，

ans[k][j-1]×next}；

{計算狀態(tài)轉(zhuǎn)移方程}end；{for}輸出最大乘積ans[n][m]；過河在河上有一座獨木橋，一只青蛙想沿著獨木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很厭煩踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨木橋上青蛙可能到達的點看成數(shù)軸上的一串整點：0，1，……，L（其中L是橋的長度）。坐標為0的點表示橋的起點，坐標為L的點表示橋的終點。青蛙從橋的起點起先，不停的向終點方向跳動。一次跳動的距離是S到T之間的隨意正整數(shù)（包括S,T）。當青蛙跳到或跳過坐標為L的點時，就算青蛙已經(jīng)跳出了獨木橋。題目給出獨木橋的長度L，青蛙跳動的距離范圍S,T，橋上石子的位置。你的任務是確定青蛙要想過河，最少須要踩到的石子數(shù)。

分析從正面來考慮的話，這個問題是一個搜尋性的問題，須要考慮從當前點動身可以跳到的全部點。然而從反面考慮的話，我們只須要考慮那些能到用一步到達當前點的全部點中，踩到石頭數(shù)最小的那個。即opt[i]=min{opt[k](max{0,i-t}≤k≤i-s)}+bri[i];代碼Fori←1tondoopt[i]=10000000;opt[0]=0;Fori←stoL+tdofork←max{0,i-t}toi-sdoif(opt[k]+bri[i]<opt[i])opt[i]=opt[k]+bri[i];以上都是線性動規(guī)的一些例題，它們的基礎時間困難度都是O(N2)裝箱問題有一個箱子容量為maxv(正整數(shù)，maxv≤20000)，同時有n件物品(0≤n≤30)，每件物品有一個體積vi(正整數(shù))。要求從這n件物品中任取若干件裝入箱內(nèi)，使箱子的剩余空間最小。分析這是一個最基礎的背包問題，只須要考慮選取哪幾個物品放入箱子，可以使得剩余體積最小。這道題的基本做法當然還是窮舉放進背包的物品編號。若我們把取該物品記為1，不取該物品記為0，那么運用某種放入方式將對應一個2進制串，因此這類問題也被稱為0-1背包問題.假如我們不從物品角度考慮，而是從體積角度考慮的話，就會發(fā)覺，這個問題還可以被描述為，w[i]的體積是否能由這些物品得到。狀態(tài)的確定我們用opt[i][j]（布爾）表示前i個物品是否能達到j體積。則opt[i][j]的值取決于前i-1個物品能否達到j體積，或者是前i-1個物品能否達到j-v[i]體積則有opt[i][j]=(opt[i-1][j-v[i]])or(opt[i-1][j])初值為opt[0][0]=true；其他都為false代碼memset(opt,0,sizeof(opt));opt[0][0]=1;for(inti=1;i<=n;i++)for(intj=0;j<=maxv;j++)if(j>=v[i]){opt[i][j]=opt[i-1][j]|opt[i-1][j-v[i]];}elseopt[i][j]=opt[i-1][j];采藥辰辰是個天資聰穎的孩子，他的幻想是成為世界上最宏大的醫(yī)師。為此，他想拜旁邊最有威望的醫(yī)師為師。醫(yī)師為了推斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都須要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。假如你是一個聰慧的孩子，你應當可以讓采到的草藥的總價值最大?！?/p>

輸入的第一行有兩個整數(shù)T(1≤T≤1000)和N(1≤N≤100)，用一個空格隔開，T代表總共能夠用來采藥的時間，N代表山洞里的草藥的數(shù)目。接下來的N行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。

分析和上面一個問題一樣，這個問題同樣可以接受搜尋解決，然而搜尋的時間困難度也同樣相當?shù)目膳隆Ｄ俏覀兛刹恍幸越梃b一下上面的想法來解決這個問題呢？狀態(tài)的確定答案是確定的。類似地，我們用opt[i][j]表示前i個物體在j時間內(nèi)的一個參數(shù)。但是我們在里面存的值并不是能否達到，而是在這個狀態(tài)下可以達到的最大價值。但是狀態(tài)的轉(zhuǎn)移方程略微有些差別，除了考慮opt[i-1][j-t[i]]和opt[i-1][j]之外，還要考慮opt[i][j-1](這樣可以最終干脆輸出opt[n][maxt]從而省掉一次掃描)，即opt[i][j]表示前i個物體在j時間內(nèi)可以達到的最大價值，留意這里包括不足j時間的狀況。代碼memset(opt,0,sizeof(opt));opt[0][0]=0;for(inti=1;i<=n;i++)for(intj=1;j<=maxt;j++)if(j>=v[i]){opt[i][j]=max{opt[i-1][j],opt[i-1][j-t[i]]+value[i],opt[i][j-1]}}elseopt[i][j]=max{opt[i-1][j],opt[i][j-1]};printf("%d\n",opt[n][maxt]);DairyQueen奶牛Bassie去DQ打工，遇到一個客人給了一張好大面值的鈔票，于是Bassie不得不為了給這位顧客找零而面對這樣一個問題：現(xiàn)在店里一共有n種硬幣，對這些不同種的硬幣進行編號，編號為i的硬幣面值為a[i]。因為奶牛的手指頭是有限的，因此他只能向你求助啦。(已知總需找零數(shù)為total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300)求一共有多少種解決方案？【輸入】第一行為硬幣總值total和硬幣種類數(shù)n。以下n行為數(shù)值a[i]，i=1,2,3...n【輸出】一行，解決方案數(shù)分析這道題目和上面的采藥的區(qū)分僅僅在于，每個物品可以無限次的取。當然，這樣的問題照舊可以用背包模型來解決，我們將這種模型稱為無限背包。在這種狀況下，我們只要把opt[i-1][j-a[i]]改成opt[i][j-a[i]],即允許一種物品被取多次。由于是計數(shù)，所以opt[i][j]=opt[i][j-a[i]]+opt[i-1][j]。一個重要的優(yōu)化：我們可以把opt數(shù)組壓縮成長度為total的一維數(shù)組，因為這樣是不會影響結(jié)果的，但可以大大降低它的空間困難度。狀態(tài)的確定我們用opt[j]表示硬幣總面值為j時共有多少種方法opt[j]=opt[j]+opt[j-a[i]](i=1,2,3..n)代碼memset(opt,0,sizeof(opt));opt[0]=1;for(inti=1;i<=n;i++) for(intj=a[i];j<=total;j++) opt[j]=opt[j]+opt[j-a[i]];printf("%d\n",opt[total]);多重背包[問題題目]有N種物品和一個容量為V的背包。第i種物品最多有m[i]件可用，每件體積是v[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包涵量，且價值總和最大。[輸入樣例]1003{maxv,n}704020{v1,v2,……,vn}504030{w1,w2,……,wn}123{m1,m2,m3……,mn}分析本題和無限背包問題很類似?；镜姆匠讨恍鑼o限背包問題的方程略微一改即可，因為對于第i種物品有m[i]+1種策略：取0件，取1件……取m[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大價值，則：f[i][v]=max{f[i-1][v-k×v[i]]+k×w[i]|0<=k<=m[i]}。時間困難度是O(V×∑m[i])。另一種好想好寫的基本方法是轉(zhuǎn)化為0-1有限背包求解：把第i種物品換成m[i]件該物品，即轉(zhuǎn)化成了物品數(shù)為∑m[i]的0-1有限背包問題，干脆求解，困難度照舊是O(V×∑m[i])。但是我們期望將它轉(zhuǎn)化為有限背包問題之后能夠降低時間困難度。分析應用二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..m[i]件——均能等價于取若干件代換以后的物品。另外，取超過m[i]件的策略必不能出現(xiàn)。方法是：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的體積和價值均是原來的體積和價值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),m[i]-2^k+1，且k是滿足m[i]-2^k+1>0的最大整數(shù)。例如，假如m[i]為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為m[i]，表明不行能取多于m[i]件。另外這種方法也能保證對于0..m[i]間的每一個整數(shù)，均可以用若干個系數(shù)的和表示。這樣就將第i種物品分成了(logm[i])種物品，將原問題轉(zhuǎn)化為了困難度為O(V×∑logm[i])的有限背包問題，是很大的改進。k=0;//轉(zhuǎn)化后物品的個數(shù)for(inti=1;i<=n;i++){//對第i件物品進行組合

intt=1;while(m[i]>0){if(m[i]>=t){k++;v1[k]=v[i]*t;w1[k]=w[i]*t;m[i]=m[i]-t;t<<=1;}else{k++;v1[k]=v[i]*m[i];w1[k]=w[i]*m[i]; m[i]=0;}}}代碼for(inti=1;i<=n;i++){//01背包，留意n是轉(zhuǎn)化后的物品個數(shù)for(intj=maxv;j>=v[i];j--){if(opt[j-v1[i]]+w1[i]>opt[j])opt[j]=opt[j-v1[i]]+w1[i];if(opt[j]>best)best=opt[j];}printf("%d\n",best);代碼以上都是背包問題的一些例題，他們的基礎時間困難度都是O(mn)的最小代價子母樹問題描述：

有n堆沙子排成一排，每堆沙子有一個數(shù)量，例如：13

7

8

16

21

4

18。隨意2堆相鄰的沙子可以進行合并，將兩堆沙子合并為一堆時，兩堆沙子數(shù)量的和稱為合并這兩堆沙子的代價。經(jīng)過不斷的歸并，最終將這些沙子歸為一堆，而全部歸并代價的和稱為總代價。例如上列數(shù)，其中2種歸并方案的代價為：第1種的總代價為20+24+25+44+69+87=267

第2種的總代價為15+37+22+28+59+87=248

由此可見，不同的歸并過程得到的總代價是不一樣的。

問題：當n個數(shù)給出后，找出一種合理的歸并方法，使得總代價最小。分析（1）假如把歸并1~4堆看成整個問題，則這個問題可以分解為三個歸并方案，每個歸并方案包含1~2個子問題：

①先歸并1~3；再與4歸并②歸并1~2，歸并3~4；再歸并③歸并2~4；再與1歸并（2）假如我們接著分析增加更多堆數(shù)進行歸并的問題，就會發(fā)覺n個數(shù)歸并時，會分解為n-1種類型：Case1:歸并第1堆，歸并2~n堆；再最終歸并Case2:歸并1~2堆，歸并3~n堆；再最終歸并……

Casen-1:歸并1~n-1堆，歸并第n堆；再最終歸并分析通過前面的分析，我們看到，歸并代價事實上由兩部分組成：（1）歸并樹左右子樹的最小代價之和（2）歸并樹全部葉結(jié)點的權(quán)值之和而對于opt數(shù)組中的子區(qū)間數(shù)值的取值大小，我們有兩種渠道來獲得：（1）利用一般的dp，枚舉起先結(jié)點和區(qū)間長度來進行DP（2）記憶化搜尋狀態(tài)的確定我們用opt[i,j]表示i-j區(qū)間合并成一堆的最小代價，則有上面的結(jié)論有opt[i][j]=min{opt[i][k]+opt[k+1][j](k=i..j-1)}+value[i..j];opt[i][i]=value[i];代碼for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)opt[i][j]=10001000;for(inti=1;i<=n;i++)opt[i][i]=value[i];a[0]=0;for(inti=1;i<=n;i++)v[i]=v[i-1]+value[i];for(intj=2;j<=n;j++)for(inti=1;i<=n-j+1;i++)for(intk=i;k<=i+j-2;k++)if(opt[i][i+j-1]>opt[i][k]+opt[k+1][i+j-1]+v[i+j-1]-v[i-1])opt[i][i+j-1]=opt[i][k]+opt[k+1][i+j-1]+v[i+j-1]-v[i-1];printf("%d\n",opt[1][n]);Power多瑞卡得到了一份好玩而高薪的工作。每天早晨他必需關(guān)掉他所在村莊的街燈。全部的街燈都被設置在一條直路的同一側(cè)。多瑞卡每晚到早晨5點鐘都在晚會上，然后他起先關(guān)燈。起先時，他站在某一盞路燈的旁邊。每盞燈都有一個給定功率的電燈泡，因為多端卡有著自覺的節(jié)能意識，他希望在耗能總數(shù)最少的狀況下將全部的燈關(guān)掉。多端卡因為太累了，所以只能以1m/s的速度行走。關(guān)燈不須要花費額外的時間，因為當他通過時就能將燈關(guān)掉。編寫程序，計算在給定路燈位置，燈泡功率以及多瑞卡的起始位置的狀況下關(guān)掉全部的燈的最少耗能。Power輸入第一行包含一個整數(shù)N，2≤N≤1000，表示該村莊路燈的數(shù)量。其次行包含一個整數(shù)V，1≤V≤N，表示多瑞卡起先關(guān)燈的路燈號碼。接下來的N行中，每行包含兩個用空格隔開的整數(shù)D和W，用來描述每盞燈的參數(shù)，其中0≤D,W≤1000。D表示該路燈與村莊起先處的距離(用米為單位來表示)，W表示燈泡的功率，每秒種該燈泡所消耗的能量數(shù)。路燈是按依次給定的。輸出一行，包含一個整數(shù)，即消耗能量之和的最小值。留意結(jié)果不超過1,000,000,000。分析首先，我們必需明確這樣一個決策：我們關(guān)掉的燈必定是一個連續(xù)的區(qū)間，也就是說，我們在路過的時候確定會把燈順手關(guān)掉，不然確定不是最優(yōu)解。而在關(guān)掉一個區(qū)間之后，我們須要作出的確定就是，回頭關(guān)另外一邊的燈還是接著朝當前方向走關(guān)前面的燈。對于我們的最終求解區(qū)間i..j,有2種可能：最終關(guān)第j盞燈，或者最終關(guān)第i盞燈。分析為了實現(xiàn)對這兩種狀況的記錄，我們須要兩個數(shù)組，分別存放關(guān)完[i,j]區(qū)間的全部路燈后分別站在兩個端點時最小的電能消耗值。并且這兩個數(shù)組中，[k][gdje]（k=1.2.3...gdje-1）區(qū)間的數(shù)值和[gdje][k](k=gdje+1...n)區(qū)間的數(shù)值都是很簡潔確定的(gdje為起先位置)。在下面的動規(guī)過程中，我們只須要決策是須要轉(zhuǎn)向另外一邊還是接著走下去就可以了。狀態(tài)的確定我們用left[i][j]表示關(guān)完燈后人站在i點所消耗的最小電能，用right[i][j]表示關(guān)完燈后人站在j點所消耗的最小電能，則有l(wèi)eft[i][j]=min{left[i+l][j]+(value[1..i]+value[j+1..n])*(pos[i+1]-pos[i]),right[i+l][j]+(value[1][i]+value[j+1..n])*(pos[j]-pos[i])};right[i][j]=min{left[i][j-1]+(value[1..i-1]+value[j..n])*(pos[j]-pos[i])),right[i][j-1]+(value[1..i-1]+value[j..n])*(pos[j]-pos[j-1])}加分二叉樹設一個n個節(jié)點的二叉樹tree的中序遍歷為(l,2,3,…,n)，其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)(均為正整數(shù))，記第i個節(jié)點的分數(shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree(也包含tree本身)的加分計算方法如下：(subtree的左子樹的加分)×(subtree的右子樹的加分)＋subtree的根的分數(shù)

若某個子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空子樹。試求一棵符合中序遍歷為(1,2,3,…,n)且加分最高的二叉樹tree。要求輸出；(1)tree的最高加分(2)tree的前序遍歷加分二叉樹【輸入格式】第1行：一個整數(shù)n(n＜30)，為節(jié)點個數(shù)。第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分數(shù)(分數(shù)＜100)【輸出格式】第1行：一個整數(shù)，為最高加分(結(jié)果不會超過4,000,000,000)。第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?571210輸出樣例14531245分析我們可以發(fā)覺這道題目給我們供應了一段序列，我們須要做的就是每次選取一個斷開的點，然后把問題遞歸地求解就可以了。這就為我們的動規(guī)供應了條件：具有最優(yōu)子結(jié)構(gòu)性質(zhì)。我們須要做出的決策，僅僅是從當前序列中選取一個點作為當前子樹的根節(jié)點，所以動規(guī)的轉(zhuǎn)移是O(n)的。狀態(tài)的確定我們用opt[i][j]表示在[i..j]區(qū)間內(nèi)可以獲得的最大加分，用root[i][j]表示[i..j]范圍內(nèi)選取哪個結(jié)點作為根時可以獲得最大加分。對區(qū)間[i,j](i>j)，我們定義opt[i][j]=1;則有：opt[i][j]=max{opt[i][k-1]*opt[k+1][j]+value[k]|k=i,i+1,i+2..j}root[i][j]為對應的k值intsearch(intl,intr){if(opt[l][r]!=0)returnopt[l][r];for(inti=l;i<=r;i++)if(search(l,i-1)*search(i+1,r)+value[i]>opt[l][r]){opt[l][r]=search(l,i-1)*search(i+1,r)+value[i];root[l][r]=i;}}memset(opt,0,sizeof(opt));for(inti=1;i<=n+1;i++)opt[i][i-1]=1;for(inti=1;i<=n;i++)opt[i][i]=value[i];intAns=search(1,n);代碼上面幾道題是區(qū)間動態(tài)規(guī)劃的一些例題，它們的基礎時間困難度都是O(N3)的聚會的快樂(Party)你要組織一個由你公司的人參與的聚會。你希望聚會特殊快樂，盡可能多地找些好玩的人。但是勸你不要同時邀請某個人和他的上司，因為這可能帶來爭吵。給定N個人（姓名，他幽默的系數(shù)，以及他上司的名字），找到能使幽默系數(shù)和最大的若干個人。輸入第一行一個整數(shù)N（N<100）。接下來有N行，每一行描述一個人，信息之間用空格隔開。姓名是長度不超過20的字符串。幽默系數(shù)是在0到100之間的整數(shù)輸出邀請的人最大的幽默系數(shù)和分析細致看過這個問題之后，會發(fā)覺這道題目和我們上面遇到的一些類型的動態(tài)規(guī)劃都有點區(qū)分：它的數(shù)據(jù)并不是以線性或者表格的形式，而是以樹的形式進行存儲的?？梢园l(fā)覺，這道題目中的關(guān)系可以簡潔地描述為：在一棵樹中，父親結(jié)點和兒子結(jié)點不行以同時選取。而每個結(jié)點有一個權(quán)值，在滿足上述條件的狀況下求出可以選取出的最大值。這就是我們所說的樹形動態(tài)規(guī)劃。由于樹本身的遞歸性質(zhì)，我們運用記憶化搜尋的方法來完成子問題答案的存儲。狀態(tài)的確定明顯，對于每個結(jié)點我們須要記錄當前結(jié)點是否被取到，以及在該種狀況下該子樹所能獲得的最大幽默系數(shù)。因此，我們定義opt[1][i]表示在編號為i的結(jié)點必取的狀況下以i為根的子樹所能獲得的最大快樂值；相應地，opt[0][i]表示在編號為i的結(jié)點不取的狀況下以i為根的子樹所能獲得的最大幽默系數(shù)。則依據(jù)題目中的要求，我們有opt[1][i]=value[i]+Σopt[0][k](k為全部i的子結(jié)點的編號)opt[0][i]=Σmax{opt[0][k],opt[1][k]}(k為全部i的子結(jié)點的編號)w數(shù)組用來存儲邊；r[i]存放編號為i的結(jié)點的兒子數(shù)；d[i]中存放編號為i的結(jié)點的在w數(shù)組中最終一條邊的編號，其中d[0]=0;d[i]=d[i-1]+r[i];intsearch(intflag,intlab){//記憶化搜尋if(opt[flag][lab]!=0)returnopt[flag][lab];intp=(flag==1)?value[lab]:0;for(inti=d[lab-1];i<=d[lab];i++)if(flag==1)p+=search(0,w[i]);elsep+=max(search(0,w[i]),search(1,w[i]));opt[flag][lab]=p;returnp;}memset(d,0,sizeof(d));for(inti=1;i<=n;i++)d[i]=d[i-1]+r[i];ans=max(search(1,root),search(0,root));代碼二*蘋果樹有一棵蘋果樹，假如樹枝有分叉，確定是分2叉（就是說沒有只有1個兒子的結(jié)點）這棵樹共有N個結(jié)點（葉子點或者樹枝分叉點），編號為1-N,樹根編號確定是1。我們用一根樹枝兩端連接的結(jié)點的編號來描述一根樹枝的位置。下面是一顆有4個樹枝的樹現(xiàn)在這顆樹枝條太多了，須要剪枝。但是一些樹枝上長有蘋果。給定須要保留的樹枝數(shù)量，求出最多能留住多少蘋果。二*蘋果樹輸入格式第1行2個數(shù)，N和Q(1<=Q<=N,1<N<=100)。N表示樹的結(jié)點數(shù)，Q表示要保留的樹枝數(shù)量。接下來N-1行描述樹枝的信息。每行3個整數(shù)，前兩個是它連接的結(jié)點的編號。第3個數(shù)是這根樹枝上蘋果的數(shù)量。

每根樹枝上的蘋果不超過30000個。輸出格式一個數(shù)，最多能留住的蘋果的數(shù)量。分析同樣，這道題目給出的數(shù)據(jù)是以樹形結(jié)構(gòu)連接的。而且這道題很明確的告知我們：每個結(jié)點只可能是葉節(jié)點或者擁有兩個兒子。因此，我們可以探討每個結(jié)點伸出的兩個樹枝的剪枝狀況，并且照舊用記憶化搜尋完成。狀態(tài)的確定我們用opt[i][j]表示編號為i的結(jié)點作為根的子樹中保留j個樹枝可以獲得的最大蘋果數(shù)。狀態(tài)轉(zhuǎn)移方程為：opt[i][j]:=maxopt[i.rc][j-1]+value[i.rc],(剪掉左枝)opt[i.lc][j-1]+value[i.lc],(剪掉右枝)max{opt[i.lc][k]+opt[i.rc][j-2-k]+value[i.lc]+value[i.rc]}(0<=k<=j-2)(左枝和右枝都不剪)intsearch(intlab,intnum){if(opt[lab][num]!=0)returnopt[lab][num];if(lc[lab]==0||num==0)return0;intl=lc[lab],r=rc[lab];if(search(r,num-1)+value[r]>opt[lab][num])opt[lab][num]=opt[r][num-1]+value[r];if(search(l,num-1)+value[l]>opt[lab][num])opt[lab][num]=opt[l][num-1]+value[i];for(inti=0;i<=num-2;i++)if(search(l,i)+search(r,num-2-i)+value[l]+value[r]>opt[lab][n