第8章動態(tài)規(guī)劃8.1動態(tài)規(guī)劃概述8.2求解整數(shù)拆分問題8.3求解最大連續(xù)子序列和問題8.4求解三角形最小路徑問題8.5求解最長公共子序列問題8.6求解最長遞增子序列問題8.7求解編輯距離問題8.8求解0/1背包問題8.9求解完全背包問題8.10求解資源分配問題8.11求解會議安排問題8.12滾動數(shù)組8.1.1從求解斐波那契數(shù)列看動態(tài)規(guī)劃法8.1動態(tài)規(guī)劃概述求解斐波那契數(shù)列的遞歸算法intcount=1; //累計調(diào)用的步驟intFib(intn) //算法{printf("(%d)求解Fib(%d)\n"，count++，n);if(n==1||n==2){printf("計算出Fib(%d)=%d\n"，n，1);return1;}else{intx=Fib(n-1);inty=Fib(n-2);

printf("計算出Fib(%d)=Fib(%d)+Fib(%d)=%d\n"， n，n-1，n-2，x+y);

returnx+y;}}Fib1(5)時的輸出結(jié)果：（1）求解Fib(5)（2）求解Fib(4)（3）求解Fib(3)（4）求解Fib(2)

計算出Fib(2)=1（5）求解Fib(1)

計算出Fib(1)=1

計算出Fib(3)=Fib(2)+Fib(1)=2（6）求解Fib(2)

計算出Fib(2)=1

計算出Fib(4)=Fib(3)+Fib(2)=3（7）求解Fib(3)（8）求解Fib(2)

計算出Fib(2)=1（9）求解Fib(1)

計算出Fib(1)=1

計算出Fib(3)=Fib(2)+Fib(1)=2

計算出Fib(5)=Fib(4)+Fib(3)=5從中看出如下幾點：（1）遞歸調(diào)用Fib(5)采用自頂向下的執(zhí)行過程，從調(diào)用Fib(5)開始到計算出Fib(5)結(jié)束。（2）計算過程中存在大量的重復(fù)計算，例如求Fib(5)的過程如圖8.1所示，存在兩次重復(fù)計算Fib(3)值的情況。Fib(5)Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(3)Fib(2)Fib(1)為此避免重復(fù)設(shè)計，設(shè)計一個dp數(shù)組，dp[i]存放Fib(i)的值，首先設(shè)置dp[1]和dp[2]均為1，再讓i從3到n循環(huán)以計算dp[3]到dp[n]的值，最后返回dp[n]即Fib1(n)。對應(yīng)的算法1如下：intdp[MAX]; //所有元素初始化為0intcount=1; //累計調(diào)用的步驟intFib1(intn) //算法1{dp[1]=dp[2]=1;printf("(%d)計算出Fib(1)=1\n"，count++);printf("(%d)計算出Fib(2)=1\n"，count++);for(inti=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];

printf("(%d)計算出Fib(%d)=%d\n"，count++，i，dp[i]);}returndp[n];}執(zhí)行Fib1(5)時的輸出結(jié)果如下：（1）計算出Fib1(1)=1（2）計算出Fib1(2)=1（3）計算出Fib1(3)=2（4）計算出Fib1(4)=3（5）計算出Fib1(5)=5其執(zhí)行過程改變?yōu)樽缘紫蛏?，即先求出子問題解，將計算結(jié)果存放在一張表中，而且相同的子問題只計算一次，在后面需要時只有簡單查表，以避免大量的重復(fù)計算。Fib(5)Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(3)查表得到查表得到上述求斐波那契數(shù)列的算法1屬于動態(tài)規(guī)劃法，其中數(shù)組dp（表）稱為動態(tài)規(guī)劃數(shù)組。動態(tài)規(guī)劃法也稱為記錄結(jié)果再利用的方法，其基本求解過程如下圖所示。原問題原問的解子問題1子問題2子問題n…填表8.1.2動態(tài)規(guī)劃的原理

動態(tài)規(guī)劃是一種解決多階段決策問題的優(yōu)化方法，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解。1.動態(tài)規(guī)劃的相關(guān)概念A(yù)B1B2B3C1C2C3D1D2E2437432653463334342

示例：在A處有一水庫，現(xiàn)需要從A點鋪設(shè)一條管道到E點，邊上的數(shù)字表示與其相連的兩個地點之間所需修建的管道長度，用c數(shù)組表示，例如c(A，B1)=2?，F(xiàn)要找出一條從A到E的修建線路，使得所需修建的管道長度最短。AB1B2B3C1C2C3D1D2E2437432653463334342

在從A～E的過程中，依據(jù)按位置所做的決策的次數(shù)及所做決策的先后次序，將問題分為5個階段，階段變量用于表示各階段，這里階段變量k為1～5，圖中第5階段是虛擬的一個邊界階段。k=1k=2k=3k=4k=5AB1B2B3C1C2C3D1D2E2437432653463334342

設(shè)最優(yōu)指標(biāo)函數(shù)f(s)表示狀態(tài)s到終點E的最短路徑長度，用k表示階段，則對應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：S2={B1，B2，B3}s2取S2的元素D2(B1)={C1，C2}x2取D2(B1)的元素符號示例2.動態(tài)規(guī)劃問題的解法逆序解法順序解法（1）動態(tài)規(guī)劃問題的逆序解法求解E→A的過程（用next表示路徑上一個頂點的后繼頂點）：AB1B2B3C1C2C3D1D2E2437432653463334342①第5階段f(E)=0②第4階段f(D1)=MIN(c(D1，E)+f(E))=3，

next(D1)=Ef(D2)=MIN(c(D2，E)+f(E))=4，

next(D2)=Ek=4f(s)表示狀態(tài)s到終點E的最短路徑長度AB1B2B3C1C2C3D1D2E2437432653463334342③第3階段k=3AB1B2B3C1C2C3D1D2E2437432653463334342④第2階段k=2AB1B2B3C1C2C3D1D2E2437432653463334342⑤第1階段k=1

由f(A)=12求出的最短路徑長度為12

由next(A)=B3，next(B3)=C2，next(C2)=D2，next(D2)=E，推出最短路徑為A→B3→C2→D2→E。（2）動態(tài)規(guī)劃問題的順序解法A→E對應(yīng)的的狀態(tài)轉(zhuǎn)移方程如下：AB1B2B3C1C2C3D1D2E2437432653463334342f(s)表示初始狀態(tài)A到狀態(tài)s的最短路徑長度用pre表示路徑上一個頂點的前驅(qū)頂點，其求解A→E的過程：AB1B2B3C1C2C3D1D2E2437432653463334342①第1階段f(A)=0②第2階段f(B1)=MIN(f(A)+c(A，B1))=2，

pre(B1)=Af(B2)=MIN(f(A)+c(A，B2))=4，

pre(B2)=Af(B3)=MIN(f(A)+c(A，B3))=3，

pre(B3)=Ak=2f(s)表示初始狀態(tài)A到狀態(tài)s的最短路徑長度AB1B2B3C1C2C3D1D2E2437432653463334342③第3階段k=3AB1B2B3C1C2C3D1D2E2437432653463334342④第4階段k=4AB1B2B3C1C2C3D1D2E2437432653463334342⑤第5階段k=4

由f(E)=12求出的最短路徑長度為12

由pre(E)=D2，pre(D2)=C2，pre(C2)=B3，pre(B3)=A，推出最短路徑為A→B3→C2→D2→E。8.1.3動態(tài)規(guī)劃求解的基本步驟能采用動態(tài)規(guī)劃求解的問題的一般要具有3個性質(zhì)：最優(yōu)性原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)性原理。f(s)表示初始狀態(tài)A到狀態(tài)s的最短路徑長度子問題的解也是最優(yōu)的tsc(t,s)f(t)f(s)無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。AB1B2B3C1C2C3D1D2E2437432653463334342k=2f(s)表示初始狀態(tài)A到狀態(tài)s的最短路徑長度k=3有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）。求斐波那契數(shù)列f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)n>2實際應(yīng)用中簡化的步驟：

分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。遞歸的定義最優(yōu)解。以自底向上或自頂向下的記憶化方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造問題的最優(yōu)解。8.1.4動態(tài)規(guī)劃與其他方法的比較

動態(tài)規(guī)劃的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。

動態(tài)規(guī)劃方法又和貪心法有些相似，在動態(tài)規(guī)劃中，可將一個問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪心法中，每采用一次貪心準(zhǔn)則便做出一個不可回溯的決策，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列。

【問題描述】求將正整數(shù)n無序拆分成最大數(shù)為k（稱為n的k拆分）的拆分方案個數(shù)，要求所有的拆分方案不重復(fù)。8.2求解整數(shù)拆分問題【問題求解】設(shè)n=5，k=5，對應(yīng)的拆分方案有：為了防止重復(fù)計數(shù)，讓拆分?jǐn)?shù)保持從大到小排序。正整數(shù)5的拆分?jǐn)?shù)為7。①5=5②5=4+1③5=3+2④5=3+1+1⑤5=2+2+1⑥5=2+1+1+1⑦5=1+1+1+1+1采用動態(tài)規(guī)劃求解整數(shù)拆分問題。設(shè)f(n，k)為n的k拆分的拆分方案個數(shù)：

（1）當(dāng)n=1，k=1時，顯然f(n，k)=1。

（2）當(dāng)n<k時，有f(n，k)=f(n，n)。

（3）當(dāng)n=k時，其拆分方案有將正整數(shù)n無序拆分成最大數(shù)為n-1的拆分方案，以及將n拆分成1個n（n=n）的拆分方案，后者僅僅一種，所以有

f(n，n)=f(n，n-1)+1。

（4）當(dāng)n>k時，根據(jù)拆分方案中是否包含k，可以分為兩種情況：

①拆分中包含k的情況：即一部分為單個k，另外一部分為{x1，x2，…，xi}，后者的和為n-k，后者中可能再次出現(xiàn)k，因此是（n-k）的k拆分，所以這種拆分方案個數(shù)為f(n-k，k)。n=k+{x1，x2，…，xi}

f(n-k，k)

②拆分中不包含k的情況：則拆分中所有拆分?jǐn)?shù)都比k小，即n的（k-1）拆分，拆分方案個數(shù)為f(n，k-1)。因此，f(n，k)=f(n-k，k)+f(n，k-1)n={x1，x2，…，xi}

f(n，k-1)最大數(shù)為k-11 當(dāng)n=1或者k=1f(n，n) 當(dāng)n<kf(n，n-1)+1 當(dāng)n=kf(n-k，k)+f(n，k-1) 其他情況f(n，k)=狀態(tài)轉(zhuǎn)移方程：顯然，求f(n，k)滿足動態(tài)規(guī)劃問題的最優(yōu)性原理、無后效性和有重疊子問題性質(zhì)。所以特別適合采用動態(tài)規(guī)劃法求解。設(shè)置動態(tài)規(guī)劃數(shù)組dp，用dp[n][k]存放f(n，k)。對應(yīng)的完整程序如下：intdp[MAXN][MAXN]; //動態(tài)規(guī)劃數(shù)組voidSplit(intn，intk) //求解算法{for(inti=1;i<=n;i++)for(intj=1;j<=k;j++){if(i==1||j==1)dp[i][j]=1;elseif(i<j)dp[i][j]=dp[i][i];elseif(i==j)dp[i][j]=dp[i][j-1]+1;elsedp[i][j]=dp[i][j-1]+dp[i-j][j];}}Split()算法計算dp[5][5]的過程：（1）dp[2][2]=dp[2][1]+1=1+1=2（2）dp[2][3]=dp[2][2]=2（3）dp[3][2]=dp[3][1]+dp[1][2]=1+1=2（4）dp[5][2]=dp[5][1]+dp[3][2]=1+2=3（5）dp[5][3]=dp[5][2]+dp[2][3]=3+2=5（6）dp[5][4]=dp[5][3]+d[1][4]=5+1=6（7）dp[5][5]=dp[5][4]+1=6+1=711111111222221233331345541356752345nk2223567實際上，該問題本身是遞歸的，可以直接采用遞歸算法實現(xiàn)!1 當(dāng)n=1或者k=1f(n，n) 當(dāng)n<kf(n，n-1)+1 當(dāng)n=kf(n-k，k)+f(n，k-1) 其他情況f(n，k)=intfun(intn，intk) //求解算法{if(n==1||k==1) return1;elseif(n<k) returnfun(n,n);elseif(n==k) returnfun(n,n-1)+1;else returnfun(n-k,k)+fun(n,k-1);}但由于子問題重疊，存在重復(fù)的計算！可以采用這樣的方法避免重復(fù)計算：設(shè)置數(shù)組dp，用dp[n][k]存放f(n，k)，首先初始化dp的所有元素為特殊值0，當(dāng)dp[n][k]不為0時表示對應(yīng)的子問題已經(jīng)求解，直接返回結(jié)果。intdp[MAXN][MAXN];intdpf(intn，intk) //求解算法{if(dp[n][k]!=0)returndp[n][k];if(n==1||k==1){ dp[n][k]=1;returndp[n][k];}elseif(n<k){ dp[n][k]=dpf(n，n);returndp[n][k];}elseif(n==k){ dp[n][k]=dpf(n，k-1)+1;returndp[n][k];}else{ dp[n][k]=dpf(n，k-1)+dpf(n-k，k);returndp[n][k];}}采用自頂向下（備忘錄方法）的動態(tài)規(guī)劃法1 當(dāng)n=1或者k=1f(n，n) 當(dāng)n<kf(n，n-1)+1 當(dāng)n=kf(n-k，k)+f(n，k-1) 其他情況f(n，k)=這種方法是一種遞歸算法，其執(zhí)行過程也是自頂向下的，但當(dāng)某個子問題解求出后，將其結(jié)果存放在一張表（dp）中，而且相同的子問題只計算一次，在后面需要時只有簡單查表，以避免大量的重復(fù)計算。這種方法稱之為備忘錄方法（memorizationmethod）。備忘錄方法是動態(tài)規(guī)劃方法的變形，與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法則是自底向上的。8.3求解最大連續(xù)子序列和問題

【問題描述】給定一個有n（n≥1）個整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。

例如

序列（-2，11，-4，13，-5，-2）的最大子序列和為20

序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和為16

規(guī)定一個序列最大連續(xù)子序列和至少是0，如果小于0，其結(jié)果為0。

【問題求解】對于含有n個整數(shù)的序列a，設(shè)

bj=MAX{ai+ai+1+…+aj}（1≤j≤n）表示a[1..j]的前j個元素中的最大連續(xù)子序列和，則bj-1表示a[1..j-1]的前j-1個元素中的最大連續(xù)子序列和。

當(dāng)bj-1>0時，bj=bj-1+aj，當(dāng)bj-1≤0時，放棄前面選取的元素，從aj開始重新選起，bj=aj。用一維動態(tài)規(guī)劃數(shù)組dp存放b，對應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：dp[0]=0 邊界條件dp[j]=MAX{dp[j-1]+aj，aj} 1≤j≤n則序列a的最大連續(xù)子序列和等于dp[j]（1≤j≤n）中的最大者。//問題表示intn=6;inta[]={0，-2，11，-4，13，-5，-2}; //a數(shù)組不用下標(biāo)為0的元素//求解結(jié)果表示intdp[MAXN];voidmaxSubSum() //求dp數(shù)組{dp[0]=0;for(intj=1;j<=n;j++) dp[j]=max(dp[j-1]+a[j]，a[j]);}voiddispmaxSum() //輸出結(jié)果{intmaxj=1;for(intj=2;j<=n;j++) //求dp中最大元素dp[maxj]if(dp[j]>dp[maxj])maxj=j;for(intk=maxj;k>=1;k--) //找前一個值小于等于0者if(dp[k]<=0)break;printf("最大連續(xù)子序列和:%d\n",dp[maxj]);printf("所選子序列:");for(inti=k+1;i<=maxj;i++)printf("%d",a[i]);printf("\n");}【算法分析】maxSubSum()的時間復(fù)雜度為O(n)。8.4求解三角形最小路徑問題

【問題描述】給定高度為n的一個整數(shù)三角形，找出從頂部到底部的最小路徑和，只能向先移動相鄰的結(jié)點。首先輸入n，接下來的1～n行，第i行輸入i個整數(shù)，輸出分為2行，第一行為最小路徑，第2行為最小路徑和。

例如，下圖是一個n=4的三角形，輸出的路徑是2353，最小路徑和是13。2345768392

【問題求解】將三角形采用二維數(shù)組a存放，前面的三角形對應(yīng)的二維數(shù)組如下：

從頂部到底部查找最小路徑，那么結(jié)點（i，j）的前驅(qū)結(jié)點只有（i-1，j-1）和（i-1，j）兩個：2345768392i，ji-1，ji-1，j-1dp[i][j]表示從頂部a[0][0]查找到（i，j）結(jié)點時的最小路徑和。i，ji-1，ji-1，j-1dp[i-1][j-1]dp[i-1][j]dp[i][j]dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j]一般情況：dp[i][j]表示從頂部a[0][0]查找到（i，j）結(jié)點時的最小路徑和。2345768392dp[i][0]=dp[i-1][0]+a[i][0]dp[i][i]=dp[i-1][i-1]+a[i][i]特殊情況：兩個邊界，即第1列和對角線，達(dá)到它們中結(jié)點的路徑只有一條而不是常規(guī)的兩條。狀態(tài)轉(zhuǎn)移方程如下：dp[0][0]=a[0][0] 頂部邊界dp[i][0]=dp[i-1][0]+a[i][0] 考慮第1列的邊界，1≤i≤n-1dp[i][i]=dp[i-1][i-1]+a[i][i] 考慮對角線的邊界，1≤i≤n-1dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j]i>1的其他有兩條達(dá)到

路徑的結(jié)點最后求出的最小路徑和ans=min(dp[n-1][j])（0≤j<n）。用pre[i][j]表示查找到（i，j）結(jié)點時最小路徑上的前驅(qū)結(jié)點，由于前驅(qū)結(jié)點只有兩個，即（i-1，j-1）和（i-1，j），用pre[i][j]記錄前驅(qū)結(jié)點的列號即可。

在求出ans后，通過pre[n-1][k]反推求出反向路徑，最后正向輸出該路徑。i，ji-1，ji-1，j-1pre[i][j]pre[i][j]=jpre[i][j]=j-1//問題表示inta[MAXN][MAXN];intn;//求解結(jié)果表示intans=0;intdp[MAXN][MAXN];intpre[MAXN][MAXN];intSearch() //求最小和路徑ans{inti，j;dp[0][0]=a[0][0];for(i=1;i<n;i++) //考慮第1列的邊界{dp[i][0]=dp[i-1][0]+a[i][0];pre[i][0]=0;}for(i=1;i<n;i++) //考慮對角線的邊界{dp[i][i]=a[i][i]+dp[i-1][i-1];pre[i][i]=i-1;}for(i=2;i<n;i++) //考慮其他有兩條達(dá)到路徑的結(jié)點{for(j=1;j<i;j++){if(dp[i-1][j-1]<dp[i-1][j]){pre[i][j]=j-1;dp[i][j]=a[i][j]+dp[i-1][j-1];}else{pre[i][j]=j;dp[i][j]=a[i][j]+dp[i-1][j];}}}i，ji-1，ji-1，j-1pre[i-1][j-1]pre[i-1][j]pre[i][j]求最小和路徑上每個結(jié)點的前驅(qū)結(jié)點ans=dp[n-1][0];intk=0;for(j=1;j<n;j++) //求出最小ans和對應(yīng)的列號k{if(ans>dp[n-1][j]){ans=dp[n-1][j];k=j;}}returnk;}返回最小和路徑最后行的列號kvoidDisppath(intk)

//輸出最小和路徑{inti=n-1;vector<int>path; //存放逆路徑向量pathwhile(i>=0) //從（n-1,k）結(jié)點反推求出反向路徑{ path.push_back(a[i][k]); k=pre[i][k]; //最小路徑在前一行中的列號 i--; //在前一行查找}vector<int>::reverse_iteratorit; //定義反向迭代器for(it=path.rbegin();it!=path.rend();++it)printf("%d",*it); //反向輸出構(gòu)成正向路徑printf("\n");}intmain(){intk;memset(pre，0，sizeof(pre));memset(dp，0，sizeof(dp));scanf("%d"，&n); //輸入三角形的高度for(inti=0;i<n;i++) //輸入三角形for(intj=0;j<=i;j++)scanf("%d"，&a[i][j]);

k=Search();

//求最小路徑和Disppath(k); //輸出正向路徑printf("%d\n"，ans); //輸出最小路徑和return0;}

【算法分析】Search()算法中有i從2到n-1、j從1到i-1的兩重循環(huán)，容易求出時間復(fù)雜度為O(n2)。

【問題描述】字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。

令給定的字符序列X=（x0，x1，…，xm-1），序列Y=（y0，y1，…，yk-1）是X的子序列，存在X的一個嚴(yán)格遞增下標(biāo)序列（i0，i1，…，ik-1），使得對所有的j=0，1，…，k-1，有=yj。8.5求解最長公共子序列問題

子序列:例如，X=（a，b，c，b，d，a，b），Y=（b，c，d，b）是X的一個子序列。

給定兩個字符序列A和B，如果字符序列Z既是A的子序列，又是B的子序列，則稱序列Z是A和B的公共子序列。該問題是求兩序列A和B的最長公共子序列（LCS）。X=（a，b，c，b，d，a，b）Y=（

b，c，d，b）

【問題求解】若設(shè)A=（a0，a1，…，am-1）（含m個字符），B=（b0，b1，…，bn-1）（含n個字符），設(shè)Z=（z0，z1，…，zk-1）（含k個字符）為它們的最長公共子序列。不難證明有以下性質(zhì)：如果am-1=bn-1，則zk-1=am-1=bn-1，且（z0，z1，…，zk-2）是（a0，a1，…，am-2）和（b0，b1，…，bn-2）的一個最長公共子序列。如果am-1≠bn-1且zk-1≠am-1，則（z0，z1，…，zk-1）是（a0，a1，…，am-2）和（b0，b1，…，bn-1）的一個最長公共子序列。如果am-1≠bn-1且zk-1≠bn-1，則（z0，z1，…，zk-1）是（a0，a1，…，am-1）和（b0，b1，…，bn-2）的一個最長公共子序列。

定義二維動態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]為子序列（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最長公共子序列的長度。

每考慮字符a[i]或b[j]都為動態(tài)規(guī)劃的一個階段（共經(jīng)歷約m×n個階段）。（a0，a1，…，ai-1）（b0，b1，…，bj-1）情況1：a[i-1]=b[j-1]（當(dāng)前兩個字符相同）dp[i][j]=dp[i-1][j-1]+1例如：abcxyby

定義二維動態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]為子序列（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最長公共子序列的長度。情況2：a[i-1]≠b[j-1]（當(dāng)前兩個字符不同）dp[i][j]=MAX(dp[i][j-1]，dp[i-1][j])（a0，a1，…，

ai-2

，

ai-1）（b0，b1，…，bj-2

，

bj-1）dp[i][j-1]dp[i-1][j]dp[i][j]為子序列（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最長公共子序列的長度。

對應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：dp[i][j]=0 i=0或j=0―邊界條件dp[i][j]=dp[i-1][j-1]+1 a[i-1]=b[j-1]dp[i][j]=MAX(dp[i][j-1]，dp[i-1][j]) a[i-1]≠b[j-1]顯然，dp[m][n]為最終結(jié)果。那么如何由dp求出LCS呢？dp

LCSdp[i][j]=0 i=0或j=0―邊界條件dp[i][j]=dp[i-1][j-1]+1 a[i-1]=b[j-1]dp[i][j]=MAX(dp[i][j-1]，dp[i-1][j]) a[i-1]≠b[j-1]當(dāng)dp[i][j]≠dp[i][j-1]（左邊）并且dp[i][j]≠dp[i-1][j]（上方）值時：

a[i-1]=b[j-1]將a[i-1]添加到LCS中。i,ji-1,ji,j-1i,ji-1,ji,j-1dp[i][j]=dp[i][j-1]：與左邊相等

j--dp[i][j]=dp[i-1][j]：與上方相等

i--與左邊、上方都不相等：a[i-1]或者b[j-1]屬于LCS

i--，j--

例如，X=（a，b，c，b，d，b），m=6，Y=（a，c，b，b，a，b，d，b，b），n=9。a00000000c01111111b01122222b01223333a01223344b01223345d01223346b01223447b01223458012234590123456abcbdbXY（1）求出dp45（2）dp[6][9]=5開始i=6，j=9LCS：dbi=6，j=8與左邊相等，j--與左、上方不等，i--，j--i=5，j=7與左、上方不等，i--，j--i=4，j=6i=4，j=5與左邊相等，j--

那么如何由dp求出LCS呢？例如，X=（a，b，c，b，d，b），m=6，Y=（a，c，b，b，a，b，d，b，b），n=9。a00000000c01111111b01122222b01223333a01223344b01223345d01223346b01223447b01223458012234590123456abcbdbXY（1）求出dp（2）dp[6][9]=5開始2345LCS：cbdbi=4，j=5i=4，j=4與左邊相等，j--i=4，j=3與左邊相等，j--與左、上方不等，i--，j--i=3，j=2與左、上方不等，i--，j--i=2，j=1

那么如何由dp求出LCS呢？例如，X=（a，b，c，b，d，b），m=6，Y=（a，c，b，b，a，b，d，b，b），n=9。a00000000c01111111b01122222b01223333a01223344b01223345d01223346b01223447b01223458012234590123456abcbdbXY（1）求出dp（2）dp[6][9]=5開始12345LCS：acbdbi=2，j=1i=1，j=1與上方相等，i--與左、上方不等，i--，j--i=0，j=0結(jié)果LCS="acbdb"#defineMAX51 //序列中最多的字符個數(shù)//問題表示intm，n;stringa，b; //求解結(jié)果表示intdp[MAX][MAX]; //動態(tài)規(guī)劃數(shù)組vector<char>subs; //存放LCSvoidLCSlength() //求dp{inti，j;for(i=0;i<=m;i++) //將dp[i][0]置為0，邊界條件dp[i][0]=0;for(j=0;j<=n;j++) //將dp[0][j]置為0，邊界條件

dp[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++) //兩重for循環(huán)處理a、b的所有字符{if(a[i-1]==b[j-1]) //情況(1)dp[i][j]=dp[i-1][j-1]+1;else //情況(2)dp[i][j]=max(dp[i][j-1]，dp[i-1][j]);}}時間復(fù)雜度為O(m×n)voidBuildsubs() //由dp構(gòu)造從subs{intk=dp[m][n]; //k為a和b的最長公共子序列長度inti=m;intj=n;while(k>0) //在subs中放入最長公共子序列(反向)if(dp[i][j]==dp[i-1][j]) i--;elseif(dp[i][j]==dp[i][j-1]) j--;else //與上方、左邊元素值均不相等{ subs.push_back(a[i-1]);//subs中添加a[i-1] i--;j--;k--;}}

【算法分析】

LCSlength算法中使用了兩重循環(huán)，所以對于長度分別為m和n的序列，求其最長公共子序列的時間復(fù)雜度為O(m×n)?？臻g復(fù)雜度為O(m×n)。8.6求解最長遞增子序列問題

【問題描述】給定一個無序的整數(shù)序列a[0..n-1]，求其中最長遞增子序列的長度。

例如，a[]={2，1，5，3，6，4，8，9，7}，n=9，其最長遞增子序列為{1，3，4，8，9}，結(jié)果為5。

【問題求解】設(shè)計動態(tài)規(guī)劃數(shù)組為一維數(shù)組dp，dp[i]表示a[0..i]中以a[i]結(jié)尾的最長遞增子序列的長度。對應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：dp[i]=1 0≤i≤n-1dp[i]=max(dp[i]，dp[j]+1) 若a[i]>a[j]，0≤i≤n-1，0≤j≤i-1求出dp后，其中最大元素即為所求。//問題表示inta[]={2，1，5，3，6，4，8，9，7};intn=sizeof(a)/sizeof(a[0]);//求解結(jié)果表示intans=0;intdp[MAX];voidsolve(inta[]，intn){inti，j;for(i=0;i<n;i++){dp[i]=1;for(j=0;j<i;j++){if(a[i]>a[j])dp[i]=max(dp[i]，dp[j]+1);}}ans=dp[0];for(i=1;i<n;i++)ans=max(ans，dp[i]);}【算法分析】solve()算法中含兩重循環(huán)，時間復(fù)雜度為O(n2)。8.7求解編輯距離問題

【問題描述】設(shè)A和B是兩個字符串。現(xiàn)在要用最少的字符操作次數(shù)，將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作共有3種：

（1）刪除一個字符。

（2）插入一個字符。

（3）將一個字符替換另一個字符。例如，A=“sfdqxbw”，B=“gfdgw”，結(jié)果為4。

【問題求解】設(shè)字符串A、B的長度分別為m、n，分別用字符串a(chǎn)、b存放。

設(shè)計一個動態(tài)規(guī)劃二維數(shù)組dp，其中dp[i][j]表示將a[0..i-1]（1≤i≤m）與b[0..j-1]（1≤j≤n）的最優(yōu)編輯距離（即a[0..i-1]轉(zhuǎn)換為b[0..j-1]的最少操作次數(shù)）。當(dāng)B串空時，要刪除A中全部字符轉(zhuǎn)換為B，即dp[i][0]=i（刪除A中i個字符，共i次操作）；當(dāng)A串空時，要在A中插入B的全部字符轉(zhuǎn)換為B，即dp[0][j]=j（向A中插入B的j個字符，共j次操作）。兩種特殊情況：

對于非空的情況，當(dāng)a[i-1]=b[j-1]時，這兩個字符不需要任何操作，即dp[i][j]=dp[i-1][j-1]。

當(dāng)a[i-1]≠b[j-1]時，以下3種操作都可以達(dá)到目的：此時dp[i][j]取3種操作的最小值。將a[i-1]替換為b[j-1]，有：dp[i][j]=dp[i-1][j-1]+1（一次替換操作的次數(shù)計為1）。在a[i-1]字符后面插入b[j-1]字符，有：dp[i][j]=dp[i][j-1]+1（一次插入操作的次數(shù)計為1）。刪除a[i-1]字符，有：dp[i][j]=dp[i-1][j]+1（一次刪除操作的次數(shù)計為1）。狀態(tài)轉(zhuǎn)移方程如下：dp[i][j]=dp[i-1][j-1] 當(dāng)a[i-1]=b[j-1]時dp[i][j]=min(dp[i-1][j-1]+1，dp[i][j-1]+1，dp[i-1][j]+1) 當(dāng)a[i-1]≠b[j-1]時最后得到的dp[m][n]即為所求。//問題表示stringa="sfdqxbw";stringb="gfdgw";//求解結(jié)果表示intdp[MAX][MAX];voidsolve() //求dp{inti，j;for(i=1;i<=a.length();i++)dp[i][0]=i; //把a(bǔ)的i個字符全部刪除轉(zhuǎn)換為bfor(j=1;j<=b.length();j++)dp[0][j]=j; //在a中插入b的全部字符轉(zhuǎn)換為bfor(i=1;i<=a.length();i++)for(j=1;j<=b.length();j++){if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(min(dp[i-1][j]，dp[i][j-1])，dp[i-1][j-1])+1;}}

【算法分析】solve()算法中有兩重循環(huán)，對應(yīng)的時間復(fù)雜度為O(mn)。8.8求解0/1背包問題

【問題描述】有n個重量分別為{w1，w2，…，wn}的物品，它們的價值分別為{v1，v2，…，vn}，給定一個容量為W的背包。

設(shè)計從這些物品中選取一部分物品放入該背包的方案，每個物品要么選中要么不選中，要求選中的物品不僅能夠放到背包中，而且重量和為W具有最大的價值。

【問題求解】對于可行的背包裝載方案，背包中物品的總重量不能超過背包的容量。

最優(yōu)方案是指所裝入的物品價值最高，即

v1*x1+v2*x2+…+vn*xn（其中xi取0或1，取1表示選取物品i）取得最大值。

在該問題中需要確定x1、x2、…、xn的值。假設(shè)按i=1，2，…，n的次序來確定xi的值，對應(yīng)n次決策即n個階段。

設(shè)置二維動態(tài)規(guī)劃數(shù)組dp，dp[i][r]表示背包剩余容量為r（1≤r≤W），已考慮物品1、2、…、i（1≤i≤n）時背包裝入物品的最優(yōu)價值。顯然對應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：這樣，dp[n][W]便是0/1背包問題的最優(yōu)解。dp[i][0]=0（背包不能裝入任何物品，總價值為0）

邊界條件dp[i][0]=0（1≤i≤n）―邊界條件dp[0][r]=0（沒有任何物品可裝入，總價值為0）

邊界條件dp[0][r]=0（1≤r≤W）―邊界條件dp[i][r]=dp[i-1][r] 當(dāng)r<w[i]時，物品i放不下dp[i][r]=MAX{dp[i-1][r]，dp[i-1][r-w[i]]+v[i]}

否則在不放入和放入物品i之間選最優(yōu)解當(dāng)dp數(shù)組計算出來后，推導(dǎo)出解向量x的過程十分簡單，從dp[n][W]開始：

（1）若dp[i][r]≠dp[i-1][r]，若dp[i][r]=dp[i-1][r-w[i]]+v[i]，置x[i]=1，累計總價值maxv+=v[i]，遞減剩余重量r=r-w[i]。

（2）若dp[i][r]=dp[i-1][r]，表示物品i放不下或者不放入物品i，置x[i]=0。dp[i][r]=dp[i-1][r] 當(dāng)r<w[i]時，物品i放不下dp[i][r]=MAX{dp[i-1][r]，dp[i-1][r-w[i]]+v[i]}

否則在不放入和放入物品i之間選最優(yōu)解

例如，某0/1背包問題為，n=5，w={2，2，6，5，4}，v={6，3，5，4，6}（下標(biāo)從1開始），W=10。求出dp：0000000000000106666620666663069999406999950669912606991012706911111580691113159012345ir06914141510邊界條件0000000000000106666620666663069999406999950699912606991012706911111580691113159012345ir06914141510回推求最優(yōu)解的過程：dp[5][10]≠dp[4][10]

x[5]=1，r=r-w[5]=6i=5，r=W=10，從dp[5][10]開始i=i-1=4，dp[4][6]=dp[3][6]

x[4]=0i=i-1=3，dp[3][6]=dp[2][6]

x[3]=0i=i-1=2，dp[2][6]≠dp[1][6]

x[2]=1，r=r-w[2]=4i=i-1=1，dp[1][4]≠dp[0][4]

x[1]=1，r=r-w[1]=21415699906x=（1，1，0，0，1），裝入物品總重量為8，總價值為15//問題表示intn=5，W=10; //5種物品，限制重量不超過10intw[MAXN]={0，2，2，6，5，4}; //下標(biāo)0不用intv[MAXN]={0，6，3，5，4，6}; //下標(biāo)0不用//求解結(jié)果表示intdp[MAXN][MAXW];intx[MAXN];intmaxv; //存放最優(yōu)解的總價值voidKnap() //動態(tài)規(guī)劃法求0/1背包問題{inti，r;for(i=0;i<=n;i++) //置邊界條件dp[i][0]=0dp[i][0]=0;for(r=0;r<=W;r++) //置邊界條件dp[0][r]=0dp[0][r]=0;for(i=1;i<=n;i++){for(r=1;r<=W;r++)if(r<w[i])dp[i][r]=dp[i-1][r];elsedp[i][r]=max(dp[i-1][r]，dp[i-1][r-w[i]]+v[i]);}}voidBuildx() //回推求最優(yōu)解{inti=n，r=W;maxv=0;while(i>=0) //判斷每個物品{if(dp[i][r]!=dp[i-1][r]){x[i]=1; //選取物品imaxv+=v[i]; //累計總價值r=r-w[i];}elsex[i]=0; //不選取物品ii--;}}

【算法分析】Knap()算法中含有兩重for循環(huán)，所以時間復(fù)雜度為O(n×W)，空間復(fù)雜度為O(n×W)。

【問題描述】有n種重量和價值分別為wi、vi（1≤i≤n）的物品，從這些物品中挑選總重量不超過W的物品，求出挑選物品價值總和最大的挑選方案，這里每種物品可以挑選任意多件。8.9求解完全背包問題

【問題求解】設(shè)置動態(tài)規(guī)劃二維數(shù)組dp，dp[i][j]表示從前i個物品中選出重量不超過j的物品的最大總價值。顯然有邊界條件：dp[i][0]=0（背包不能裝入任何物品時，總價值為0），dp[0][j]=0（沒有任何物品可裝入時，總價值為0）→采用memset函數(shù)一次性初始化為0。另外設(shè)置二維數(shù)組fk，其中fk[i][j]存放dp[i][j]得到最大值時物品i挑選的件數(shù)。狀態(tài)轉(zhuǎn)移方程：dp[i][j]=MAX{dp[i-1][j-k*w[i]]+k*v[i]}當(dāng)dp[i][j]<dp[i-1][j-k*w[i]]+k*v[i]（k*w[i]≤j）fk[i][j]=k;

物品i取k件

這樣，dp[n][W]便是背包容量為W、考慮所有n個物品（同一物品允許多次選擇）后得到的背包最大總價值，即問題的最優(yōu)結(jié)果。例如，n=3，W=7，w=(3，4，2)，v=(4，5，3)時，其求解結(jié)果如下表所示，表中元素為dp(i，j)[fk(i，j)]，dp(n，W)為最終結(jié)果，即最大價值總和為10。

ji0123456700[0]0[0]0[0]0[0]0[0]0[0]0[0]0[0]10[0]0[0]0[0]4[1]4[1]4[1]8[2]8[2]20[0]0[0]0[0]4[0]5[1]5[1]8[0]9[1]30[0]0[0]3[1]4[0]6[1]7[1]9[3]10[2]回推過程：（1）i=3；dp[3][7]=10，fk[3][7]=2，物品3挑選2件（2）i=2；dp[2][W-2×2]=dp[2][3]=4,fk[2][3]=0，物品2挑選0件（3）i=1；dp[1][3]=4,fk[1][3]=1，物品1挑選1件。//問題表示intn,W;intw[MAXN],v[MAXN];//求解結(jié)果表示intdp[MAXN+1][MAXW+1],fk[MAXN+1][MAXW+1];intsolve() //求解多重背包問題{inti,j,k;for(i=1;i<=n;i++){for(j=0;j<=W;j++)for(k=0;k*w[i]<=j;k++){if(dp[i][j]<dp[i-1][j-k*w[i]]+k*v[i]){dp[i][j]=dp[i-1][j-k*w[i]]+k*v[i];fk[i][j]=k; //物品i取k件}}}returndp[n][W];}voidTraceback() //回推求最優(yōu)解{inti=n,j=W;while(i>=1){printf("物品%d共%d件",i,fk[i][j]);j-=fk[i][j]*w[i]; //剩余重量i--;}printf("\n");}

【算法分析】solve算法有三重循環(huán)，k的循環(huán)最壞可能從0到W，所以算法的時間復(fù)雜度為O(nW2)。

【算法改進(jìn)】實際上，上述算法中不必使用k循環(huán)，可以修改為在挑選物品i時直接多次重復(fù)挑選。

因為計算dp[i][j]中選擇k（k≥1）個的情況與在dp[i][j-w[i]]的計算中選擇k-1個的情況是相同的，所以dp[i][j]的遞推中k≥1部分的計算已經(jīng)在dp[i][j-w[i]]的計算中完成了。intsolve1() //動態(tài)規(guī)劃法求完全背包問題{inti,k,j;for(i=1;i<=n;i++)for(j=0;j<=W;j++){if(j<w[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);}returndp[n][W];

//返回總價值}該算法的時間復(fù)雜度為O(nW)。

【問題描述】資源分配問題是將數(shù)量一定的一種或若干種資源（原材料、資金、設(shè)備或勞動力等），合理地分配給若干使用者，使總收益最大。

例如，某公司有3個商店A、B、C，擬將新招聘的5名員工分配給這3個商店，各商店得到新員工后，每年的贏利情況如下表所示，求分配給各商店各多少員工才能使公司的贏利最大？員工數(shù)商店0人1人2人3人4人5人A03791213B0510111111C0461112128.10求解資源分配問題

【問題求解】采用動態(tài)規(guī)劃求解該問題。設(shè)置3個商店A、B、C的編號分別為1～3。

這里總員工數(shù)為n=5，商店個數(shù)m=3，假設(shè)從商店3開始決策起。

設(shè)置二維動態(tài)規(guī)劃數(shù)組為dp，其中dp[i][s]表示考慮商店i～商店m并分配s個人后的最優(yōu)贏利。

另外設(shè)置二維數(shù)組pnum，其中pnum[i][s]表示求出dp[i][s]時對應(yīng)商店i的分配人數(shù)。對應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：顯然，dp[1][n]就是最優(yōu)贏利。dp[m+1][j]=0 邊界條件（類似終點的dp值為0）dp[i][s]=max(v[i][j]+dp[i+1][s-j]) pnum[i][s]=dp[i][s]取最大值

的j（0≤j≤n）//問題表示intm=3,n=5; //商店數(shù)為m,總?cè)藬?shù)為nintv[MAXM][MAXN]={{0,0,0,0,0,0},{0,3,7,9,12,13}, {0,5,10,11,11,11},{0,4,6,11,12,12}};//不計v[0]行//求解結(jié)果表示intdp[MAXM][MAXN];intpnum[MAXM][MAXN];voidPlan() //求最優(yōu)方案dp{intmaxf,maxj;for(intj=0;j<=n;j++) //置邊界條件dp[m+1][j]=0;for(inti=m;i>=1;i--) //i從商店3到1進(jìn)行處理{for(ints=1;s<=n;s++)