動(dòng)態(tài)規(guī)劃教程(c語(yǔ)言描述)

第九課動(dòng)態(tài)規(guī)劃綜合實(shí)踐考核數(shù)字三角形1、問(wèn)題描述上圖給出了一個(gè)數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對(duì)于每條路徑，把路徑上面的數(shù)加起來(lái)可以得到一個(gè)和，和最大的路徑稱為最佳路徑。你的任務(wù)就是求出最佳路徑上的數(shù)字之和。注意：路徑上的每一步只能從一個(gè)數(shù)走到下一層上和它最近的左邊的數(shù)或者右邊的數(shù)。問(wèn)題描述輸入數(shù)據(jù)輸入的第一行是一個(gè)整數(shù)N(1<N<=100)，給出三角形的行數(shù)。下面的N行給出數(shù)字三角形。數(shù)字三角形上的數(shù)的范圍都在0和100之間。輸出要求輸出最大的和。問(wèn)題描述輸入樣例5738810274445265輸出樣例302、解題思路這道題目可以用遞歸的方法解決?；舅悸肥牵阂訢(r,j)表示第r行第j個(gè)數(shù)字(r，j都從1開(kāi)始算)，以MaxSum(r,j)代表從第r行的第j個(gè)數(shù)字到底邊的最佳路徑的數(shù)字之和，則本題是要求MaxSum(1,1)。從某個(gè)D(r,j)出發(fā)，顯然下一步只能走D(r+1,j)或者D(r+1,j+1)。如果走D(r+1,j)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j)+D(r,j)；如果走D(r+1,j+1)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j+1)+D(r,j)。所以，選擇往哪里走，就看MaxSum(r+1,j)和MaxSum(r+1,j+1)哪個(gè)更大了。3、參考程序I#include<stdio.h>#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intMaxSum(intr,intj){ if(r==N) returnD[r][j]; intnSum1=MaxSum(r+1,j); intnSum2=MaxSum(r+1,j+1);

if(nSum1>nSum2) returnnSum1+D[r][j]; returnnSum2+D[r][j];}3、參考程序Iintmain(void){ intm; scanf("%d",&N); for(inti=1;i<=N;i++) for(intj=1;j<=i;j++) scanf("%d",&D[i][j]); printf("%d",MaxSum(1,1)); return0;}提交結(jié)果：TimeLimitExceed程序I分析上面的程序，效率非常低，在N值并不大，比如N=100的時(shí)候，就慢得幾乎永遠(yuǎn)算不出結(jié)果了。為什么會(huì)這樣呢？是因?yàn)檫^(guò)多的重復(fù)計(jì)算。我們不妨將對(duì)MaxSum函數(shù)的一次調(diào)用稱為一次計(jì)算。那么，每次計(jì)算MaxSum(r,j)的時(shí)候，都要計(jì)算一次MaxSum(r+1,j+1)，而每次計(jì)算MaxSum(r,j+1)的時(shí)候，也要計(jì)算一次MaxSum(r+1,j+1)。重復(fù)計(jì)算因此產(chǎn)生。在題目中給出的例子里，如果我們將MaxSum(r,j)被計(jì)算的次數(shù)都寫在位置（r,j），那么就能得到右面的三角形：111121133114641738810274445265程序分析

從上圖可以看出，最后一行的計(jì)算次數(shù)總和是16，倒數(shù)第二行的計(jì)算次數(shù)總和是8。不難總結(jié)出規(guī)律，對(duì)于N行的三角形，總的計(jì)算次數(shù)是2^0+2^1+2^2+…+2^(N-1)=2^N-1。當(dāng)N=100時(shí)，總的計(jì)算次數(shù)是一個(gè)讓人無(wú)法接受的大數(shù)字。既然問(wèn)題出在重復(fù)計(jì)算，那么解決的辦法，當(dāng)然就是，一個(gè)值一旦算出來(lái)，就要記住，以后不必重新計(jì)算。即第一次算出MaxSum(r,j)的值時(shí)，就將該值存放起來(lái)，下次再需要計(jì)算MaxSum(r,j)時(shí)，直接取用存好的值即可，不必再次調(diào)用MaxSum進(jìn)行函數(shù)遞歸計(jì)算了。這樣，每個(gè)MaxSum(r,j)都只需要計(jì)算1次即可，那么總的計(jì)算次數(shù)（即調(diào)用MaxSum函數(shù)的次數(shù)）就是三角形中的數(shù)字總數(shù)，即1+2+3+…+N=N(N+1)/2。如何存放計(jì)算出來(lái)的MaxSum（r,j）值呢？顯然，用一個(gè)二維數(shù)組aMaxSum[N][N]就能解決。aMaxSum[r][j]就存放MaxSum(r,j)的計(jì)算結(jié)果。下次再需要MaxSum(r,j)的值時(shí)，不必再調(diào)用MaxSum函數(shù)，只需直接取aMaxSum[r][j]的值即可。4、參考程序II#include<stdio.h>#include<memory.h>#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intaMaxSum[MAX_NUM+10][MAX_NUM+10];intMaxSum(intr,intj){if(r==N)returnD[r][j];if(aMaxSum[r+1][j]==-1)//如果MaxSum(r+1,j)沒(méi)有計(jì)算過(guò)

aMaxSum[r+1][j]=MaxSum(r+1,j);if(aMaxSum[r+1][j+1]==-1)aMaxSum[r+1][j+1]=MaxSum(r+1,j+1);if(aMaxSum[r+1][j]>aMaxSum[r+1][j+1])returnaMaxSum[r+1][j]+D[r][j];returnaMaxSum[r+1][j+1]+D[r][j];}4、參考程序IIintmain(void){intm;scanf("%d",&N);//將aMaxSum全部置成-1,開(kāi)始時(shí)所有的MaxSum(r,j)都沒(méi)有算過(guò)

memset(aMaxSum,-1,sizeof(aMaxSum));for(inti=1;i<=N;i++)for(intj=1;j<=i;j++)scanf("%d",&D[i][j]);printf("%d",MaxSum(1,1));return0;}程序II分析

這種將一個(gè)問(wèn)題分解為子問(wèn)題遞歸求解，并且將中間結(jié)果保存以避免重復(fù)計(jì)算的辦法，就叫做“動(dòng)態(tài)規(guī)劃”。動(dòng)態(tài)規(guī)劃通常用來(lái)求最優(yōu)解，能用動(dòng)態(tài)規(guī)劃解決的求最優(yōu)解問(wèn)題，必須滿足，最優(yōu)解的每個(gè)局部解也都是最優(yōu)的。以上題為例，最佳路徑上面的每個(gè)數(shù)字到底部的那一段路徑，都是從該數(shù)字出發(fā)到達(dá)到底部的最佳路徑。實(shí)際上，遞歸的思想在編程時(shí)未必要實(shí)現(xiàn)為遞歸函數(shù)。在上面的例子里，有遞推公式：因此，不需要寫遞歸函數(shù)，從aMaxSum[N-1]這一行元素開(kāi)始向上逐行遞推，就能求得aMaxSum[1][1]的值了。5、參考程序IIIintD[MAX_NUM+10][MAX_NUM+10];intN;intaMaxSum[MAX_NUM+10][MAX_NUM+10];intmain(void){inti,j;scanf("%d",&N);for(i=1;i<=N;i++)for(j=1;j<=i;j++)scanf("%d",&D[i][j]);for(j=1;j<=N;j++)aMaxSum[N][j]=D[N][j];for(i=N;i>1;i--)for(j=1;j<i;j++){if(aMaxSum[i][j]>aMaxSum[i][j+1])aMaxSum[i-1][j]=aMaxSum[i][j]+D[i-1][j];elseaMaxSum[i-1][j]=aMaxSum[i][j+1]+D[i-1][j];}printf("%d",aMaxSum[1][1]);return0;}思考題：上面的幾個(gè)程序只算出了最佳路徑的數(shù)字之和。如果要求輸出最佳路徑上的每個(gè)數(shù)字，該怎么辦？動(dòng)態(tài)規(guī)劃解題的一般思路

許多求最優(yōu)解的問(wèn)題可以用動(dòng)態(tài)規(guī)劃來(lái)解決。首先要把原問(wèn)題分解為若干個(gè)子問(wèn)題。注意單純的遞歸往往會(huì)導(dǎo)致子問(wèn)題被重復(fù)計(jì)算，用動(dòng)態(tài)規(guī)劃的方法，子問(wèn)題的解一旦求出就要被保存，所以每個(gè)子問(wèn)題只需求解一次。子問(wèn)題經(jīng)常和原問(wèn)題形式相似，有時(shí)甚至完全一樣，只不過(guò)規(guī)模從原來(lái)的n變成了n-1，或從原來(lái)的n×m變成了n×(m-1)……等等。找到子問(wèn)題，就意味著找到了將整個(gè)問(wèn)題逐漸分解的辦法。分解下去，直到最底層規(guī)模最小的的子問(wèn)題可以一目了然地看出解。每一層子問(wèn)題的解決，會(huì)導(dǎo)致上一層子問(wèn)題的解決，逐層向上，就會(huì)導(dǎo)致最終整個(gè)問(wèn)題的解決。如果從最底層的子問(wèn)題開(kāi)始，自底向上地推導(dǎo)出一個(gè)個(gè)子問(wèn)題的解，那么編程的時(shí)候就不需要寫遞歸函數(shù)。動(dòng)態(tài)規(guī)劃解題的一般思路

用動(dòng)態(tài)規(guī)劃解題時(shí)，將和子問(wèn)題相關(guān)的各個(gè)變量的一組取值，稱之為一個(gè)“狀態(tài)”。一個(gè)“狀態(tài)”對(duì)應(yīng)于一個(gè)或多個(gè)子問(wèn)題，所謂某個(gè)“狀態(tài)”下的“值”，就是這個(gè)“狀態(tài)”所對(duì)應(yīng)的子問(wèn)題的解。比如數(shù)字三角形，子問(wèn)題就是“從位于(r，j)數(shù)字開(kāi)始，到底邊路徑的最大和”。這個(gè)子問(wèn)題和兩個(gè)變量r和j相關(guān)，那么一個(gè)“狀態(tài)”，就是r,j的一組取值，即每個(gè)數(shù)字的位置就是一個(gè)“狀態(tài)”。該“狀態(tài)”所對(duì)應(yīng)的“值”，就是從該位置的數(shù)字開(kāi)始，到底邊的最佳路徑上的數(shù)字之和。定義出什么是“狀態(tài)”，以及在該“狀態(tài)”下的“值”后，就要找出不同的狀態(tài)之間如何遷移――即如何從一個(gè)或多個(gè)“值”已知的“狀態(tài)”，求出另一個(gè)“狀態(tài)”的“值”。狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)轉(zhuǎn)移方程”。動(dòng)態(tài)規(guī)劃解題的一般思路用動(dòng)態(tài)規(guī)劃解題，如何尋找“子問(wèn)題”，定義“狀態(tài)”，“狀態(tài)轉(zhuǎn)移方程”是什么樣的，并沒(méi)有一定之規(guī)，需要具體問(wèn)題具體分析，題目做多了就會(huì)有感覺(jué)。甚至，對(duì)于同一個(gè)問(wèn)題，分解成子問(wèn)題的辦法可能不止一種，因而“狀態(tài)”也可以有不同的定義方法。不同的“狀態(tài)”定義方法可能會(huì)導(dǎo)致時(shí)間、空間效率上的區(qū)別。最長(zhǎng)上升子序列1、問(wèn)題描述

一個(gè)數(shù)的序列bi，當(dāng)b1<b2<...<bS

的時(shí)候，我們稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(a1,a2,...,aN)，我們可以得到一些上升的子序列(ai1,ai2,...,aiK)，這里1<=i1<i2<...<iK<=N。比如，對(duì)于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4，比如子序列(1,3,5,8).你的任務(wù)，就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。問(wèn)題描述輸入數(shù)據(jù)輸入的第一行是序列的長(zhǎng)度N(1<=N<=1000)。第二行給出序列中的N個(gè)整數(shù)，這些整數(shù)的取值范圍都在0到10000。輸出要求最長(zhǎng)上升子序列的長(zhǎng)度。輸入樣例71735948輸出樣例42、解題思路

如何把這個(gè)問(wèn)題分解成子問(wèn)題呢？經(jīng)過(guò)分析，發(fā)現(xiàn)“求以ak（k=1,2,3…N）為終點(diǎn)的最長(zhǎng)上升子序列的長(zhǎng)度”是個(gè)好的子問(wèn)題――這里把一個(gè)上升子序列中最右邊的那個(gè)數(shù)，稱為該子序列的“終點(diǎn)”。雖然這個(gè)子問(wèn)題和原問(wèn)題形式上并不完全一樣，但是只要這N個(gè)子問(wèn)題都解決了，那么這N個(gè)子問(wèn)題的解中，最大的那個(gè)就是整個(gè)問(wèn)題的解。由上所述的子問(wèn)題只和一個(gè)變量相關(guān)，就是數(shù)字的位置。因此序列中數(shù)的位置k就是“狀態(tài)”，而狀態(tài)k對(duì)應(yīng)的“值”，就是以ak做為“終點(diǎn)”的最長(zhǎng)上升子序列的長(zhǎng)度。這個(gè)問(wèn)題的狀態(tài)一共有N個(gè)。狀態(tài)定義出來(lái)后，轉(zhuǎn)移方程就不難想了。2、解題思路假定MaxLen(k)表示以ak

做為“終點(diǎn)”的最長(zhǎng)上升子序列的長(zhǎng)度，那么：MaxLen(1)=1MaxLen(k)=Max{MaxLen(i)：1<i<k且

ai<ak

且

k≠1}+1這個(gè)狀態(tài)轉(zhuǎn)移方程的意思就是，MaxLen(k)的值，就是在ak

左邊，“終點(diǎn)”數(shù)值小于ak，且長(zhǎng)度最大的那個(gè)上升子序列的長(zhǎng)度再加1。因?yàn)閍k

左邊任何“終點(diǎn)”小于ak

的子序列，加上ak

后就能形成一個(gè)更長(zhǎng)的上升子序列。實(shí)際實(shí)現(xiàn)的時(shí)候，可以不必編寫遞歸函數(shù)，因?yàn)閺?/p>

MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3)……3、參考程序intb[MAX_N+10];intaMaxLen[MAX_N+10];intmain(void){inti,j,N;scanf("%d",&N);for(i=1;i<=N;i++)scanf("%d",&b[i]);aMaxLen[1]=1;3、參考程序for(i=2;i<=N;i++){//求以第i個(gè)數(shù)為終點(diǎn)的最長(zhǎng)上升子序列的長(zhǎng)度

intnTmp=0;//記錄第i個(gè)數(shù)左邊子序列最大長(zhǎng)度

for(j=1;j<i;j++){//搜索以第i個(gè)數(shù)左邊數(shù)為終點(diǎn)的最長(zhǎng)上升子序列長(zhǎng)度

if(b[i]>b[j]){if(nTmp<aMaxLen[j])nTmp=aMaxLen[j];}}aMaxLen[i]=nTmp+1;}intnMax=-1;for(i=1;i<=N;i++)if(nMax<aMaxLen[i])nMax=aMaxLen[i];printf("%d\n",nMax);return0;}思考題：改進(jìn)此程序，使之能夠輸出最長(zhǎng)上升子序列HelpJimmy1、問(wèn)題描述"HelpJimmy"是在下圖所示的場(chǎng)景上完成的游戲：?jiǎn)栴}描述

場(chǎng)景中包括多個(gè)長(zhǎng)度和高度各不相同的平臺(tái)。地面是最低的平臺(tái)，高度為零，長(zhǎng)度無(wú)限。

Jimmy老鼠在時(shí)刻0從高于所有平臺(tái)的某處開(kāi)始下落，它的下落速度始終為1米/秒。當(dāng)Jimmy落到某個(gè)平臺(tái)上時(shí)，游戲者選擇讓它向左還是向右跑，它跑動(dòng)的速度也是1米/秒。當(dāng)Jimmy跑到平臺(tái)的邊緣時(shí)，開(kāi)始繼續(xù)下落。Jimmy每次下落的高度不能超過(guò)MAX米，不然就會(huì)摔死，游戲也會(huì)結(jié)束。設(shè)計(jì)一個(gè)程序，計(jì)算Jimmy到地面時(shí)可能的最早時(shí)間。問(wèn)題描述輸入數(shù)據(jù)第一行是測(cè)試數(shù)據(jù)的組數(shù)t（0<=t<=20）。每組測(cè)試數(shù)據(jù)的第一行是四個(gè)整數(shù)N，X，Y，MAX，用空格分隔。N是平臺(tái)的數(shù)目（不包括地面），X和Y是Jimmy開(kāi)始下落的位置的橫豎坐標(biāo)，MAX是一次下落的最大高度。接下來(lái)的N行每行描述一個(gè)平臺(tái)，包括三個(gè)整數(shù)，X1[i]，X2[i]和H[i]。H[i]表示平臺(tái)的高度，X1[i]和X2[i]表示平臺(tái)左右端點(diǎn)的橫坐標(biāo)。1<=N<=1000，-20000<=X,X1[i],X2[i]<=20000，0<H[i]<Y<=20000（i=1..N）。所有坐標(biāo)的單位都是米。

Jimmy的大小和平臺(tái)的厚度均忽略不計(jì)。如果Jimmy恰好落在某個(gè)平臺(tái)的邊緣，被視為落在平臺(tái)上。所有的平臺(tái)均不重疊或相連。測(cè)試數(shù)據(jù)保Jimmy一定能安全到達(dá)地面。問(wèn)題描述輸出要求對(duì)輸入的每組測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)，Jimmy到地面時(shí)可能的最早時(shí)間。輸入樣例13817200108010134143輸出樣例232、解題思路

此題目的“子問(wèn)題”是什么呢？

Jimmy跳到一塊板上后，可以有兩種選擇，向左走或向右走。走到左端和走到右端所需的時(shí)間，容易算出。如果我們能知道，以左端為起點(diǎn)到達(dá)地面的最短時(shí)間，和以右端為起點(diǎn)到達(dá)地面的最短時(shí)間，那么向左走還是向右走，就很容選擇了。因此，整個(gè)問(wèn)題就被分解成兩個(gè)子問(wèn)題，即Jimmy所在位置下方第一塊板左端為起點(diǎn)到地面的最短時(shí)間，和右端為起點(diǎn)到地面的最短時(shí)間。這兩個(gè)子問(wèn)題在形式上和原問(wèn)題是完全一致的。將板子從上到下從1開(kāi)始進(jìn)行無(wú)重復(fù)的編號(hào)(高度相同的板子，哪塊編號(hào)在前無(wú)所謂)，那么，和上面兩個(gè)子問(wèn)題相關(guān)的變量就只有板子的編號(hào)。2、解題思路

所以，本題目的“狀態(tài)”就是板子編號(hào)，而一個(gè)“狀態(tài)”對(duì)應(yīng)的“值”有兩部分，是兩個(gè)子問(wèn)題的解，即從該板子左端出發(fā)到達(dá)地面的最短時(shí)間，和從該板子右端出發(fā)到達(dá)地面的最短時(shí)間。不妨認(rèn)為Jimmy開(kāi)始的位置是一個(gè)編號(hào)為0，長(zhǎng)度為0的板子，假設(shè)LeftMinTime(k)表示從k號(hào)板子左端到地面的最短時(shí)間，RightMinTime(k)表示從k號(hào)板子右端到地面的最短時(shí)間，那么，求板子k左端點(diǎn)到地面的最短時(shí)間的方法如下：if(板子k左端正下方?jīng)]有別的板子){if(板子k的高度h(k)大于Max)LeftMinTime(k)=∞;elseLeftMinTime(k)=h(k);}elseif(板子k左端正下方的板子編號(hào)是m)LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k));2、解題思路

上面，h(i)就代表i號(hào)板子的高度，Lx(i)就代表i號(hào)板子左端點(diǎn)的橫坐標(biāo)，Rx(i)就代表i號(hào)板子右端點(diǎn)的橫坐標(biāo)。那么h(k)-h(m)當(dāng)然就是從k號(hào)板子跳到m號(hào)板子所需要的時(shí)間，Lx(k)-Lx(m)就是從m號(hào)板子的落腳點(diǎn)走到m號(hào)板子左端點(diǎn)的時(shí)間，Rx(m)-Lx(k)就是從m號(hào)板子的落腳點(diǎn)走到右端點(diǎn)所需的時(shí)間。求RightMinTime(k)的過(guò)程類似。不妨認(rèn)為Jimmy開(kāi)始的位置是一個(gè)編號(hào)為0，長(zhǎng)度為0的板子，那么整個(gè)問(wèn)題就是要求LeftMinTime(0)。輸入數(shù)據(jù)中，板子并沒(méi)有按高度排序，所以程序中一定要首先將板子排序。3、參考程序#include<stdio.h>#include<memory.h>#include<stdlib.h>#defineMAX_N1000#defineINFINITE1000000intt,n,x,y,max;structPlatform{intLx,Rx,h;};PlatformaPlatform[MAX_N+10];intaLeftMinTime[MAX_N+10];intaRightMinTime[MAX_N+10];intMyCompare(constvoid*e1,constvoid*e2){Platform*p1,*p2;p1=(Platform*)e1;p2=(Platform*)e2;returnp2->h-p1->h;//從大到小排列}3、參考程序intMinTime(intL,boolbLeft){inty=aPlatform[L].h;inti,x;if(bLeft)x=aPlatform[L].Lx;elsex=aPlatform[L].Rx;for(i=L+1;i<=n;i++)//找到下一張板子

{if(aPlatform[i].Lx<=x&&aPlatform[i].Rx>=x)break;}if(i<=n)//找到了

{if(y-aPlatform[i].h>max)//太高

returnINFINITE;}3、參考程序else//沒(méi)找到

{if(y>max)//離地面太高

returnINFINITE;elsereturny;}//特殊情況處理完畢

intnLeftTime=y-aPlatform[i].h+x-aPlatform[i].Lx;intnRightTime=y-aPlatform[i].h+aPlatform[i].Rx-x;if(aLeftMinTime[i]==-1)//還沒(méi)有存儲(chǔ)值

aLeftMinTime[i]=MinTime(i,true);if(aRightMinTime[i]==-1)aRightMinTime[i]=MinTime(i,false);nLeftTime+=aLeftMinTime[i];nRightTime+=aRightMinTime[i];if(nLeftTime<nRightTime)returnnLeftTime;returnnRightTime;}3、參考程序intmain(void){scanf("%d",&t);for(inti=0;i<t;i++){memset(aLeftMinTime,-1,sizeof(aLeftMinTime));memset(aRightMinTime,-1,sizeof(aRightMinTime));scanf("%d%d%d%d",&n,&x,&y,&max);aPlatform[0].Lx=x;aPlatform[0].Rx=x;//長(zhǎng)度為0的板子aPlatform[0].h=y;for(intj=1;j<=n;j++)scanf("%d%d%d",&aPlatform[j].Lx,

&aPlatform[j].Rx,&aPlatform[j].h);qsort(aPlatform,n+1,sizeof(Platform),MyCompare);printf("%d\n",MinTime(0,true));}return0;}思考題：重新編寫此程序，要求不使用遞歸函數(shù)最長(zhǎng)公共子序列1、問(wèn)題描述

我們稱序列Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列<i1,i2,...,ik>，使得對(duì)j=1,2,...,k,有xij=zj。比如Z=<a,b,f,c>是X=<a,b,c,f,b,c>的子序列?，F(xiàn)在給出兩個(gè)序列X和Y，你的任務(wù)是找到X和Y的最大公共子序列，也就是說(shuō)要找到一個(gè)最長(zhǎng)的序列Z，使得Z既是X的子序列也是Y的子序列。輸入數(shù)據(jù)輸入包括多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個(gè)長(zhǎng)度不超過(guò)200的字符串，表示兩個(gè)序列。兩個(gè)字符串之間由若干個(gè)空格隔開(kāi)。問(wèn)題描述

輸出要求對(duì)每組輸入數(shù)據(jù)，輸出一行，給出兩個(gè)序列的最大公共子序列的長(zhǎng)度。輸入樣例

abcfbcabfcabprogrammingcontestabcdmnp

輸出樣例

4202、解題思路用字符數(shù)組s1、s2存放兩個(gè)字符串，用s1[i]表示s1中的第i個(gè)字符，s2[j]表示s2中的第j個(gè)字符（字符編號(hào)從1開(kāi)始），用s1i表示s1的前i個(gè)字符所構(gòu)成的子串，s2j表示s2的前j個(gè)字符構(gòu)成的子串，MaxLen(i,j)表示s1i

和s2j

的最長(zhǎng)公共子序列的長(zhǎng)度，那么遞推關(guān)系如下：if(i==0||j==0)MaxLen(i,j)=0//兩個(gè)空串的最長(zhǎng)公共子序列長(zhǎng)度是0elseif(s1[i]==s2[j])MaxLen(i,j)=MaxLen(i-1,j-1)+1;elseMaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j));2、解題思路

顯然本題目的“狀態(tài)”就是s1中的位置i和s2中的位置j?！爸怠本褪荕axLen(i,j)。狀態(tài)的數(shù)目是s1長(zhǎng)度和s2長(zhǎng)度的乘積?？梢杂靡粋€(gè)二維數(shù)組來(lái)存儲(chǔ)各個(gè)狀態(tài)下的“值”。本問(wèn)題的兩個(gè)子問(wèn)題，和原問(wèn)題形式完全一致的，只不過(guò)規(guī)模小了一點(diǎn)。3、參考程序#include<stdio.h>#include<string.h>#defineMAX_LEN1000charsz1[MAX_LEN];charsz2[MAX_LEN];intaMaxLen[MAX_LEN][MAX_LEN];intmain(void){while(scanf("%s%s",sz1+1,sz2+1)>0){intnLength1=strlen(sz1+1);intnLength2=strlen(sz2+1);inti,j;for(i=0;i<=nLength1;i++)aMaxLen[i][0]=0;for(j=0;j<=nLength2;j++)aMaxLen[0][j]=0;3、參考程序

for(i=1;i<=nLength1;i++){for(j=1;j<=nLength2;j++){if(sz1[i]==sz2[j])aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;else{intnLen1=aMaxLen[i][j-1];intnLen2=aMaxLen[i-1][j];if(nLen1>nLen2)aMaxLen[i][j]=nLen1;elseaMaxLen[i][j]=nLen2;}}}printf("%d\n",aMaxLen[nLength1][nLength2]);}return0;}陪審團(tuán)的人選1、問(wèn)題描述

在遙遠(yuǎn)的國(guó)家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決定。陪審團(tuán)是由法官?gòu)墓娭刑暨x的。先隨機(jī)挑選n個(gè)人作為陪審團(tuán)的候選人，然后再?gòu)倪@n個(gè)人中選m人組成陪審團(tuán)。選m人的辦法是：控方和辯方會(huì)根據(jù)對(duì)候選人的喜歡程度，給所有候選人打分，分值從0到20。為了公平起見(jiàn)，法官選出陪審團(tuán)的原則是：選出的m個(gè)人，必須滿足辯方總分和控方總分的差的絕對(duì)值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對(duì)值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團(tuán)方案。問(wèn)題描述輸入數(shù)據(jù)輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行是兩個(gè)整數(shù)n和m，n是候選人數(shù)目，m是陪審團(tuán)人數(shù)。注意，1<=n<=200,1<=m<=20而且m<=n。接下來(lái)的n行，每行表示一個(gè)候選人的信息，它包含2個(gè)整數(shù)，先后是控方和辯方對(duì)該候選人的打分。候選人按出現(xiàn)的先后從1開(kāi)始編號(hào)。兩組有效數(shù)據(jù)之間以空行分隔。最后一組數(shù)據(jù)n=m=0輸出要求對(duì)每組數(shù)據(jù)，先輸出一行，表示答案所屬的組號(hào),如'Jury#1','Jury#2',等。接下來(lái)的一行要象例子那樣輸出陪審團(tuán)的控方總分和辯方總分。再下來(lái)一行要以升序輸出陪審團(tuán)里每個(gè)成員的編號(hào)，兩個(gè)成員編號(hào)之間用空格分隔。每組輸出數(shù)據(jù)須以一個(gè)空行結(jié)束。問(wèn)題描述輸入樣例421223416200輸出樣例Jury#1Bestjuryhasvalue6forprosecutionandvalue4fordefence:232、解題思路為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡(jiǎn)稱為“辯控差”，辯方總分和控方總分之和稱為“辯控和”。第i個(gè)候選人的辯方總分和控方總分之差記為V(i)，辯方總分和控方總分之和記為S(i)?，F(xiàn)用f(j,k)表示，取j個(gè)候選人，使其辯控差為k的所有方案中，辯控和最大的那個(gè)方案（該方案稱為“方案f(j,k)”）的辯控和。并且，我們還規(guī)定，如果沒(méi)法選j個(gè)人，使其辯控差為k，那么f(j,k)的值就為-1，也稱方案f(j,k)不可行。本題是要求選出m個(gè)人，那么，如果對(duì)k的所有可能的取值，求出了所有的f(m,k)(-20×m≤k≤20×m)，那么陪審團(tuán)方案自然就很容易找到了。2、解題思路問(wèn)題的關(guān)鍵是建立遞推關(guān)系。顯然，方案f(j,k)是由某個(gè)可行的方案f(j-1,x)(-20×m≤x≤20×m)演化而來(lái)的?？尚蟹桨竑(j-1,x)能演化成方案f(j,k)的必要條件是：存在某個(gè)候選人i，i在方案f(j-1,x)中沒(méi)有被選上，且x+V(i)=k。在所有滿足該必要條件的f(j-1,x)中，選出

f(j-1,x)+S(i)的值最大的那個(gè)，那么方案f(j-1,x)再加上候選人i，就演變成了方案

f(j,k)。由上面知一個(gè)方案都選了哪些人需要全部記錄下來(lái)。不妨將方案f(j,k)中最后選的那個(gè)候選人的編號(hào)，記在二維數(shù)組的元素path[j][k]中。那么方案f(j,k)的倒數(shù)第二個(gè)人選的編號(hào)，就是path[j-1][k-V[path[j][k]]]。假定最后算出了方案的辯控差是k，那么從path[m][k]出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。2、解題思路初始條件，只能確定f(0,0)=0。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案f(m,k)(-20×m≤k≤20×m)。實(shí)際解題的時(shí)候，會(huì)用一個(gè)二維數(shù)組f來(lái)存放f(j,k)的值。而且，由于題目中辯控差的值k可以為負(fù)數(shù)，而程序中數(shù)租下標(biāo)不能為負(fù)數(shù)，所以，在程序中不妨將辯控差的值都加上20×m，以免下標(biāo)為負(fù)數(shù)導(dǎo)致出錯(cuò)，即題目描述中，如果辯控差為0，則在程序中辯控差為20×m。3、參考程序#include<stdio.h>#include<stdlib.h>#include<memory.h>intf[30][1000];intPath[30][1000];intP[300];//控方打分intD[300];//辯方打分intAnswer[30];//存放最終方案的人選intCompareInt(constvoid*e1,constvoid*e2){return*((int*)e1)-*((int*)e2);}3、參考程序intmain(void){inti,j,k;intt1,t2;intn,m;intnMinP_D;//辯控雙方總分一樣時(shí)的辯控差intnCaseNo;//測(cè)試數(shù)據(jù)編號(hào)nCaseNo=0;scanf("%d%d",&n,&m);while(n+m){nCaseNo++;for(i=1;i<=n;i++)scanf("%d%d",&P[i],&D[i]);memset(f,-1,sizeof(f));memset(Path,0,sizeof(Path));nMinP_D=m*20;//題目中的辯控差為0//對(duì)應(yīng)到程序中辯控差就是m*20f[0][nMinP_D]=0;//選0個(gè)人辯控差為0的方案，其辯控和就是03、參考程序

for(j=0;j<m;j++){//每次循環(huán)選出第j個(gè)人，共要選出m人for(k=0;k<=nMinP_D*2;k++)//辯控差的范圍是[0,nMinP_D*2]{if(f[j][k]>=0){//方案f(j,k)可行for(i=1;i<=n;i++)//由所有f(j,k)，確定f(j+1,*){//*表示可能的辯控差if(f[j][k]+P[i]+D[i]>f[j+1][k+P[i]-D[i]]){//即時(shí)判別記住更合適的f(j,k)t1=j;t2=k;while(t1>0&&Path[t1][t2]!=i){//t2減去編號(hào)為Path[t1][t2]的辯控差t2-=P[Path[t1][t2]]-D[Path[t1][t2]];t1--;//減少1人}if(t1==0)//沒(méi)有發(fā)現(xiàn){f[j+1][k+P[i]-D[i]]=f[j][k]+P[i]+D[i];Path[j+1][k+P[i]-D[i]]=i;}}}}}}3、參考程序

i=nMinP_D;j=0;while(f[m][i+j]<0&&f[m][i-j]<0)//從中間向左右同時(shí)找j++;if(f[m][i+j]>f[m][i-j])//絕對(duì)值相同時(shí)找辯控和最大的k=i+j;elsek=i-j;printf("Jury#%d\n",nCaseNo);printf("Bestjuryhasvalue%dforprosecutionandvalue

%dfordefence:\n",(k-nMinP_D+f[m][k])/2,

(f[m][k]-k+nMinP_D)/2);for(i=1;i<=m;i++){Answer[i]=Path[m-i+1][k];k-=P[Answer[i]]-D[Answer[i]];//減去辯控差}qsort(Answer+1,m,sizeof(int),CompareInt);for(i=1;i<=m;i++)printf("%d",Answer[i]);printf("\n");printf("\n");scanf("%d%d",&n,&m);}return0;}最長(zhǎng)公共子序列1、問(wèn)題描述

我們稱序列Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列<i1,i2,...,ik>，使得對(duì)j=1,2,...,k,有xij=zj。比如Z=<a,b,f,c>是X=<a,b,c,f,b,c>的子序列?，F(xiàn)在給出兩個(gè)序列X和Y，你的任務(wù)是找到X和Y的最大公共子序列，也就是說(shuō)要找到一個(gè)最長(zhǎng)的序列Z，使得Z既是X的子序列也是Y的子序列。輸入數(shù)據(jù)輸入包括多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個(gè)長(zhǎng)度不超過(guò)200的字符串，表示兩個(gè)序列。兩個(gè)字符串之間由若干個(gè)空格隔開(kāi)。問(wèn)題描述

輸出要求對(duì)每組輸入數(shù)據(jù)，輸出一行，給出兩個(gè)序列的最大公共子序列的長(zhǎng)度。輸入樣例

abcfbcabfcabprogrammingcontestabcdmnp

輸出樣例

4202、解題思路用字符數(shù)組s1、s2存放兩個(gè)字符串，用s1[i]表示s1中的第i個(gè)字符，s2[j]表示s2中的第j個(gè)字符（字符編號(hào)從1開(kāi)始），用s1i表示s1的前i個(gè)字符所構(gòu)成的子串，s2j表示s2的前j個(gè)字符構(gòu)成的子串，MaxLen(i,j)表示s1i

和s2j

的最長(zhǎng)公共子序列的長(zhǎng)度，那么遞推關(guān)系如下：if(i==0||j==0)MaxLen(i,j)=0//兩個(gè)空串的最長(zhǎng)公共子序列長(zhǎng)度是0elseif(s1[i]==s2[j])MaxLen(i,j)=MaxLen(i-1,j-1)+1;elseMaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j));2、解題思路

顯然本題目的“狀態(tài)”就是s1中的位置i和s2中的位置j?！爸怠本褪荕axLen(i,j)。狀態(tài)的數(shù)目是s1長(zhǎng)度和s2長(zhǎng)度的乘積?？梢杂靡粋€(gè)二維數(shù)組來(lái)存儲(chǔ)各個(gè)狀態(tài)下的“值”。本問(wèn)題的兩個(gè)子問(wèn)題，和原問(wèn)題形式完全一致的，只不過(guò)規(guī)模小了一點(diǎn)。3、參考程序#include<stdio.h>#include<string.h>#defineMAX_LEN1000charsz1[MAX_LEN];charsz2[MAX_LEN];intaMaxLen[MAX_LEN][MAX_LEN];intmain(void){while(scanf("%s%s",sz1+1,sz2+1)>0){intnLength1=strlen(sz1+1);intnLength2=strlen(sz2+1);inti,j;for(i=0;i<=nLength1;i++)aMaxLen[i][0]=0;for(j=0;j<=nLength2;j++)aMaxLen[0][j]=0;3、參考程序

for(i=1;i<=nLength1;i++){for(j=1;j<=nLength2;j++){if(sz1[i]==sz2[j])aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;else{intnLen1=aMaxLen[i][j-1];intnLen2=aMaxLen[i-1][j];if(nLen1>nLen2)aMaxLen[i][j]=nLen1;elseaMaxLen[i][j]=nLen2;}}}printf("%d\n",aMaxLen[nLength1][nLength2]);}return0;}陪審團(tuán)的人選1、問(wèn)題描述

在遙遠(yuǎn)的國(guó)家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決定。陪審團(tuán)是由法官?gòu)墓娭刑暨x的。先隨機(jī)挑選n個(gè)人作為陪審團(tuán)的候選人，然后再?gòu)倪@n個(gè)人中選m人組成陪審團(tuán)。選m人的辦法是：控方和辯方會(huì)根據(jù)對(duì)候選人的喜歡程度，給所有候選人打分，分值從0到20。為了公平起見(jiàn)，法官選出陪審團(tuán)的原則是：選出的m個(gè)人，必須滿足辯方總分和控方總分的差的絕對(duì)值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對(duì)值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團(tuán)方案。問(wèn)題描述輸入數(shù)據(jù)輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行是兩個(gè)整數(shù)n和m，n是候選人數(shù)目，m是陪審團(tuán)人數(shù)。注意，1<=n<=200,1<=m<=20而且m<=n。接下來(lái)的n行，每行表示一個(gè)候選人的信息，它包含2個(gè)整數(shù)，先后是控方和辯方對(duì)該候選人的打分。候選人按出現(xiàn)的先后從1開(kāi)始編號(hào)。兩組有效數(shù)據(jù)之間以空行分隔。最后一組數(shù)據(jù)n=m=0輸出要求對(duì)每組數(shù)據(jù)，先輸出一行，表示答案所屬的組號(hào),如'Jury#1','Jury#2',等。接下來(lái)的一行要象例子那樣輸出陪審團(tuán)的控方總分和辯方總分。再下來(lái)一行要以升序輸出陪審團(tuán)里每個(gè)成員的編號(hào)，兩個(gè)成員編號(hào)之間用空格分隔。每組輸出數(shù)據(jù)須以一個(gè)空行結(jié)束。問(wèn)題描述輸入樣例421223416200輸出樣例Jury#1Bestjuryhasvalue6forprosecutionandvalue4fordefence:232、解題思路為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡(jiǎn)稱為“辯控差”，辯方總分和控方總分之和稱為“辯控和”。第i個(gè)候選人的辯方總分和控方總分之差記為V(i)，辯方總分和控方總分之和記為S(i)?，F(xiàn)用f(j,k)表示，取j個(gè)候選人，使其辯控差為k的所有方案中，辯控和最大的那個(gè)方案（該方案稱為“方案f(j,k)”）的辯控和。并且，我們還規(guī)定，如果沒(méi)法選j個(gè)人，使其辯控差為k，那么f(j,k)的值就為-1，也稱方案f(j,k)不可行。本題是要求選出m個(gè)人，那么，如果對(duì)k的所有可能的取值，求出了所有的f(m,k)(-20×m≤k≤20×m)，那么陪審團(tuán)方案自然就很容易找到了。2、解題思路問(wèn)題的關(guān)鍵是建立遞推關(guān)系。顯然，方案f(j,k)是由某個(gè)可行的方案f(j-1,x)(-20×m≤x≤20×m)演化而來(lái)的?？尚蟹桨竑(j-1,x)能演化成方案f(j,k)的必要條件是：存在某個(gè)候選人i，i在方案f(j-1,x)中沒(méi)有被選上，且x+V(i)=k。在所有滿足該必要條件的f(j-1,x)中，選出

f(j-1,x)+S(i)的值最大的那個(gè)，那么方案f(j-1,x)再加上候選人i，就演變成了方案

f(j,k)。由上面知一個(gè)方案都選了哪些人需要全部記錄下來(lái)。不妨將方案f(j,k)中最后選的那個(gè)候選人的編號(hào)，記在二維數(shù)組的元素path[j][k]中。那么方案f(j,k)的倒數(shù)第二個(gè)人選的編號(hào)，就是path[j-1][k-V[path[j][k]]]。假定最后算出了方案的辯控差是k，那么從path[m][k]出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。2、解題思路初始條件，只能確定f(0,0)=0。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案f(m,k)(-20×m≤k≤20×m)。實(shí)際解題的時(shí)候，會(huì)用一個(gè)二維數(shù)組f來(lái)存放f(j,k)的值。而且，由于題目中辯控差的值k可以為負(fù)數(shù)，而程序中數(shù)租下標(biāo)不能為負(fù)數(shù)，所以，在程序中不妨將辯控差的值都加上20×m，以免下標(biāo)為負(fù)數(shù)導(dǎo)致出錯(cuò)，即題目描述中，如果辯控差為0，則在程序中辯控差為20×m。3、參考程序#include<stdio.h>#include<stdlib.h>#include<memory.h>intf[30][1000];intPath[30][1000];intP[300];//控方打分intD[300];//辯方打分intAnswer[30];//存放最終方案的人選intCompareInt(constvoid*e1,constvoid*e2){return*((int*)e1)-*((int*)e2);}3、參考程序intmain(void){inti,j,k;intt1,t2;intn,m;intnMinP_D;//辯控雙方總分一樣時(shí)的辯控差intnCaseNo;//測(cè)試數(shù)據(jù)編號(hào)nCaseNo=0;scanf("%d%d",&n,&m);while(n+m){nCaseNo++;for(i=1;i<=n;i++)scanf("%d%d",&P[i],&D[i]);memset(f,-1,sizeof(f));memset(Path,0,sizeof(Path));nMinP_D=m*20;//題目中的辯控差為0//對(duì)應(yīng)到程序中辯控差就是m*20f[0][nMinP_D]=0;//選0個(gè)人辯控差為0的方案，其辯控和就是03、參考程序

for(j=0;j<m;j++){//每次循環(huán)選出第j個(gè)人，共要選出m人for(k=0;k<=nMinP_D*2;k++)//辯控差的范圍是[0,nMinP_D*2]{if(f[j][k]>=0){//方案f(j,k)可行for(i=1;i<=n;i++)//由所有f(j,k)，確定f(j+1,*){

//*表示可能的辯控差if(f[j][k]+P[i]+D[i]>f[j+1][k+P[i]-D[i]]){//即時(shí)判別記住更合適的f(j,k)t1=j;t2=k;while(t1>0&&Path[t1][t2]!=i){//t2減去編號(hào)為Path[t1][t2]的辯控差t2-=P[Path[t1][t2]]-D[Path[t1][t2]];t1--;//減少1人}if(t1==0)//沒(méi)有發(fā)現(xiàn){f[j+1][k+P[i]-D[i]]=f[j][k]+P[i]+D[i];Path[j+1][k+P[i]-D[i]]=i;}}}}}}3、參考程序

i=nMinP_D;j=0;while(f[m][i+j]<0&&f[m][i-j]<0)//從中間向左右同時(shí)找j++;if(f[m][i+j]>f[m][i-j])//絕對(duì)值相同時(shí)找辯控和最大的k=i+j;elsek=i-j;printf("Jury#%d\n",nCaseNo);printf("Bestjuryhasvalue%dforprosecutionandvalue

%dfordefence:\n",(k-nMinP_D+f[m][k])/2,

(f[m][k]-k+nMinP_D)/2);for(i=1;i<=m;i++){Answer[i]=Path[m-i+1][k];k-=P[Answer[i]]-D[Answer[i]];//減去辯控差}qsort(Answer+1,m,sizeof(int),CompareInt);for(i=1;i<=m;i++)printf("%d",Answer[i]);printf("\n");printf("\n");scanf("%d%d",&n,&m);}return0;}購(gòu)物問(wèn)題1、問(wèn)題描述由于換季，ACM商場(chǎng)推出優(yōu)惠活動(dòng)，以超低價(jià)格出售若干種商品。但是，商場(chǎng)為避免過(guò)分虧本，規(guī)定某些商品不能同時(shí)購(gòu)買，而且每種超低價(jià)商品只能買一件。身為顧客的你想獲得最大的實(shí)惠，也就是爭(zhēng)取節(jié)省最多的錢。經(jīng)過(guò)仔細(xì)研究過(guò)，我們發(fā)現(xiàn)，商場(chǎng)出售的超低價(jià)商品中，不存在以下這種情況：N(3<=n)種商品C1,C2,…,Cn，其中Ci和Ci+1是不能同時(shí)購(gòu)買的(i=1,2,…,n-1)，而且C1和Cn也不能同時(shí)購(gòu)買。請(qǐng)編程計(jì)算可以節(jié)省的最大金額數(shù)。問(wèn)題描述輸入數(shù)據(jù)第1行兩個(gè)整數(shù)K,M(1<=k<=1000)，其中K表示超低價(jià)商品數(shù)，K種商品的編號(hào)依次為1,2,…,K；M表示不能同時(shí)購(gòu)買的商品對(duì)數(shù)。接下來(lái)K行，第i行有一個(gè)整數(shù)Xi表示購(gòu)買編號(hào)為i的商品可以節(jié)省的金額(1<=Xi<=100)。再接下來(lái)M行，每行兩個(gè)數(shù)A和B，表示A和B不能同時(shí)購(gòu)買，1<=A<=K，1<=B<=K，A≠B。

輸出要求僅一個(gè)整數(shù)，表示能節(jié)省的最大金額數(shù)。問(wèn)題描述輸入樣例3111112輸出樣例22、解題思路

本題關(guān)鍵是構(gòu)造一個(gè)結(jié)點(diǎn)帶權(quán)的圖，結(jié)點(diǎn)表示超低價(jià)商品，結(jié)點(diǎn)的權(quán)值表示購(gòu)買該商品能節(jié)省的金額，邊表示邊所連的兩個(gè)點(diǎn)的商品不能同時(shí)購(gòu)買。這樣就相當(dāng)于在圖中找出一個(gè)點(diǎn)集，使該點(diǎn)集中任兩點(diǎn)沒(méi)有連邊而且權(quán)值之和最大。依題意，該圖是無(wú)環(huán)圖，所以該圖由若干棵樹(shù)組成。只要把每棵樹(shù)的相應(yīng)最大節(jié)省金額求出來(lái)再求和即得結(jié)果。2、解題思路對(duì)于單棵樹(shù)，可以用動(dòng)態(tài)規(guī)劃的方法求出結(jié)