由以上的分析可知，該算法的分割步驟和合并步驟總共耗時(shí)O(n)。因此，算法耗費(fèi)的計(jì)算時(shí)間T(n)滿足遞歸方程：
解此遞歸方程可得T(n)=O(nlogn)。
【問題】循環(huán)賽日程表
問題描述：設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽�，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：
（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次；
（2）每個(gè)選手一天只能參賽一次；
（3）循環(huán)賽在n-1天內(nèi)結(jié)束。
請(qǐng)按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個(gè)表。在表中的第i行，第j列處填入第i個(gè)選手在第j天所遇到的選手。其中1≤i≤n，1≤j≤n-1。
按分治策略，我們可以將所有的選手分為兩半，則n個(gè)選手的比賽日程表可以通過n/2個(gè)選手的比賽日程表來決定。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 |
4 |
3 |
6 |
7 |
8 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
4 |
1 |
2 |
7 |
8 |
5 |
6 |
|
|
|
|
|
|
|
1 |
2 |
3 |
|
|
|
4 |
3 |
2 |
1 |
8 |
5 |
6 |
7 |
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
5 |
6 |
7 |
8 |
1 |
4 |
3 |
2 |
|
|
1 |
|
|
|
2 |
1 |
4 |
3 |
|
|
|
6 |
5 |
8 |
7 |
2 |
1 |
4 |
3 |
|
1 |
2 |
|
|
|
3 |
4 |
1 |
2 |
|
|
|
7 |
8 |
5 |
6 |
3 |
2 |
1 |
4 |
|
2 |
1 |
|
|
|
4 |
3 |
2 |
1 |
|
|
|
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
（1） （2） （3）
圖1 2個(gè)、4個(gè)和8個(gè)選手的比賽日程表
圖1所列出的正方形表（3）是8個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對(duì)位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對(duì)位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個(gè)比賽日程表推廣到具有任意多個(gè)選手的情形。
八、動(dòng)態(tài)規(guī)劃法
經(jīng)常會(huì)遇到復(fù)雜問題不能簡(jiǎn)單地分解成幾個(gè)子問題，而會(huì)分解出一系列的子問題。簡(jiǎn)單地采用把大問題分解成子問題，并綜合子問題的解導(dǎo)出大問題的解的方法，問題求解耗時(shí)會(huì)按問題規(guī)模呈冪級(jí)數(shù)增加。
為了節(jié)約重復(fù)求相同子問題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問題的解存于該數(shù)組中，這就是動(dòng)態(tài)規(guī)劃法所采用的基本方法。以下先用實(shí)例說明動(dòng)態(tài)規(guī)劃方法的使用。
【問題】 求兩字符序列的最長(zhǎng)公共字符子序列
問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列<i0，i1，…，ik-1>，使得對(duì)所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列。
給定兩個(gè)序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長(zhǎng)公共子序列。
如采用列舉A的所有子序列，并一一檢查其是否又是B的子序列，并隨時(shí)記錄所發(fā)現(xiàn)的子序列，最終求出最長(zhǎng)公共子序列。這種方法因耗時(shí)太多而不可取。
考慮最長(zhǎng)公共子序列問題如何分解成子問題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列。
這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個(gè)最長(zhǎng)公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。
定義c[i][j]為序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最長(zhǎng)公共子序列的長(zhǎng)度，計(jì)算c[i][j]可遞歸地表述如下：
（1）c[i][j]=0 如果i=0或j=0；
（2）c[i][j]= c[i-1][j-1]+1 如果I，j>0，且a[i-1]=b[j-1]；
（3）c[i][j]=max（c[i][j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
按此算式可寫出計(jì)算兩個(gè)序列的最長(zhǎng)公共子序列的長(zhǎng)度函數(shù)。由于c[i][j]的產(chǎn)生僅依賴于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以從c[m][n]開始，跟蹤c[i][j]的產(chǎn)生過程，逆向構(gòu)造出最長(zhǎng)公共子序列。細(xì)節(jié)見程序。
# include <stdio.h>
# include <string.h>
# define N 100
char a[N],b[N],str[N];
int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[i][0]=0;
for (i=0;i<=n;i++) c[0][i]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
return c[m][n];
}
char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’\0’;
while (k>0)
if (c[i][j]==c[i-1][j]) i--;
else if (c[i][j]==c[i][j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}
void main()
{ printf (“Enter two string（<%d）!\n”,N);
scanf(“%s%s”,a,b);
printf(“LCS=%s\n”,build_lcs(str,a,b));
}
1、動(dòng)態(tài)規(guī)劃的適用條件
任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。
（1）最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）
最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
圖2
例如圖2中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑J’是B到C的最優(yōu)路徑，則A到C的路線取I和J’比I和J更優(yōu)，矛盾。從而證明J’必是B到C的最優(yōu)路徑。
最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。根據(jù)最優(yōu)化原理導(dǎo)出的動(dòng)態(tài)規(guī)劃基本方程是解決一切動(dòng)態(tài)規(guī)劃問題的基本方法。
（2）無后向性
將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無后向性，又稱為無后效性。
（3）子問題的重疊性
動(dòng)態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。選擇動(dòng)態(tài)規(guī)劃算法是因?yàn)閯?dòng)態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時(shí)間上卻無法承受，所以我們舍空間而取時(shí)間。
所以，能夠用動(dòng)態(tài)規(guī)劃解決的問題還有一個(gè)顯著特征：子問題的重疊性。這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。
2、動(dòng)態(tài)規(guī)劃的基本思想
前文主要介紹了動(dòng)態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動(dòng)態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃是在研究多階段決策問題時(shí)推導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。
動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。
由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問題是獨(dú)立的（即不包含公共的子子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。
解決上述問題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或最�。┲档慕�。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇，該方法對(duì)每一個(gè)子問題只解一次，并將結(jié)果保存起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。
因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必重新求解。
3、動(dòng)態(tài)規(guī)劃算法的基本步驟
設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通�？砂匆韵聨讉�(gè)步驟進(jìn)行：
（1）劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動(dòng)態(tài)規(guī)劃求解。
（2）選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。
（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實(shí)上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。
（4）寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。
一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡(jiǎn)單的。動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。根據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算，實(shí)現(xiàn)的大體上的框架如下：
標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃的基本框架
1. 對(duì)fn+1(xn+1)初始化; {邊界條件}
for k:=n downto 1 do
for 每一個(gè)xk∈Xk do
for 每一個(gè)uk∈Uk(xk) do
begin
5. fk(xk):=一個(gè)極值; {∞或－∞}
6. xk+1:=Tk(xk,uk); {狀態(tài)轉(zhuǎn)移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
if t比fk(xk)更優(yōu) then fk(xk):=t; {計(jì)算fk(xk)的最優(yōu)值}
end;
9. t:=一個(gè)極值; {∞或－∞}
for 每一個(gè)x1∈X1 do
11. if f1(x1)比t更優(yōu) then t:=f1(x1); {按照10式求出最優(yōu)指標(biāo)}
12. 輸出t;
但是，實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)步驟進(jìn)行：
（1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。
（2）遞歸地定義最優(yōu)值。
（3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。
（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。
步驟（1）～（3）是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4）。此時(shí)，在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。
【問題】 凸多邊形的最優(yōu)三角剖分問題
問題描述：多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點(diǎn)稱為多邊形的頂點(diǎn)。若多邊形的邊之間除了連接頂點(diǎn)外沒有別的公共點(diǎn)，則稱該多邊形為簡(jiǎn)單多邊形。一個(gè)簡(jiǎn)單多邊形將平面分為3個(gè)部分：被包圍在多邊形內(nèi)的所有點(diǎn)構(gòu)成了多邊形的內(nèi)部；多邊形本身構(gòu)成多邊形的邊界；而平面上其余的點(diǎn)構(gòu)成了多邊形的外部。當(dāng)一個(gè)簡(jiǎn)單多邊形及其內(nèi)部構(gòu)成一個(gè)閉凸集時(shí)，稱該簡(jiǎn)單多邊形為凸多邊形。也就是說凸多邊形邊界上或內(nèi)部的任意兩點(diǎn)所連成的直線段上所有的點(diǎn)均在該凸多邊形的內(nèi)部或邊界上。
通常，用多邊形頂點(diǎn)的逆時(shí)針序列來表示一個(gè)凸多邊形，即P=<v0，v1，…，vn-1>表示具有n條邊v0v1，v1v2，…，vn-1vn的一個(gè)凸多邊形，其中，約定v0=vn 。
若vi與vj是多邊形上不相鄰的兩個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個(gè)子多邊形<vi，vi+1，…，vj>和<vj，vj+1，…，vi>。多邊形的三角剖分是一個(gè)將多邊形分割成互不重迭的三角形的弦的集合T。圖1是一個(gè)凸多邊形的兩個(gè)不同的三角剖分。
|
|
|
|
(a) |
(b) |
圖1 一個(gè)凸多邊形的2個(gè)不同的三角剖分
在凸多邊形P的一個(gè)三角剖分T中，各弦互不相交且弦數(shù)已達(dá)到最大，即P的任一不在T中的弦必與T中某一弦相交。在一個(gè)有n個(gè)頂點(diǎn)的凸多邊形的三角刮分中，恰好有n-3條弦和n-2個(gè)三角形。
凸多邊形最優(yōu)三角剖分的問題是：給定一個(gè)凸多邊形P=<v0，v1，…，vn-1>以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)ω。要求確定該凸多邊形的一個(gè)三角剖分，使得該三角剖分對(duì)應(yīng)的權(quán)即剖分中諸三角形上的權(quán)之和為最小。
可以定義三角形上各種各樣的權(quán)函數(shù)ω。例如：定義ω(△vivjvk)=| vivj |+| vivk |+| vkvj |，其中，| vivj |是點(diǎn)vi到vj的歐氏距離。相應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長(zhǎng)三角剖分。
（1）最優(yōu)子結(jié)構(gòu)性質(zhì)
凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若凸（n+1）邊形P=<v0，v1 ，…，vn>的一個(gè)最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和，即三角形v0vkvn的權(quán)，子多邊形<v0，v1，…，vk>的權(quán)和<vk，vk+1，…，vn>的權(quán)之和�？梢詳嘌杂�T所確定的這兩個(gè)子多邊形的三角剖分也是最優(yōu)的，因?yàn)槿粲?/SPAN><v0，v1，…，vk>或<vk，vk+1，…，vn>的更小權(quán)的三角剖分，將會(huì)導(dǎo)致T不是最優(yōu)三角剖分的矛盾。
（2）最優(yōu)三角剖分對(duì)應(yīng)的權(quán)的遞歸結(jié)構(gòu)
首先，定義t[i，j]（1≤i<j≤n）為凸子多邊形<vi-1，vi，…，vj>的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)值，即最優(yōu)值。為方便起見，設(shè)退化的多邊形<vi-1，vi>具有權(quán)值0。據(jù)此定義，要計(jì)算的凸（n+1）邊多邊形P對(duì)應(yīng)的權(quán)的最優(yōu)值為t[1，n]。
t[i，j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。由于退化的2頂點(diǎn)多邊形的權(quán)值為0，所以t[i，i]=0，i=1，2，…，n 。當(dāng)j一i≥1時(shí)，子多邊形<vi-1，vi，…，vj>至少有3個(gè)頂點(diǎn)。由最優(yōu)于結(jié)構(gòu)性質(zhì)，t[i，j]的值應(yīng)為t[i，k]的值加上t[k+1，j]的值，再加上△vi-1vkvj的權(quán)值，并在i≤k≤j-1的范圍內(nèi)取最小。由此，t[i，j]可遞歸地定義為：
（3）計(jì)算最優(yōu)值
下面描述的計(jì)算凸（n+1）邊形P=<v0，v1，…，vn>的三角剖分最優(yōu)權(quán)值的動(dòng)態(tài)規(guī)劃算法MINIMUM_WEIGHT，輸入是凸多邊形P=<v0，v1，…，vn>的權(quán)函數(shù)ω，輸出是最優(yōu)值t[i，j]和使得t[i，k]+t[k+1，j]+ω（△vi-1vkvj）達(dá)到最優(yōu)的位置（k=）s[i，j]，1≤i≤j≤n 。
Procedure MINIMUM_WEIGHT(P，w)；
Begin
n=length[p]-1;
for i=1 to n do t[i,i]:=0;
for ll=2 to n do
for i=1 to n-ll+1 do
begin
j=i+ll-1;
t[i,j]=∞;
for k=i to j-1 do
begin
q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
if q<t[i,j] then
begin
t[i,j]=q;
s[i,j]=k;
end;
end;
end;
return(t,s);
end;
算法MINIMUM_WEIGHT_占用θ(n2)空間，耗時(shí)θ(n3)。
（4）構(gòu)造最優(yōu)三角剖分
如我們所看到的，對(duì)于任意的1≤i≤j≤n ，算法MINIMUM_WEIGHT在計(jì)算每一個(gè)子多邊形<vi-1，vi，…，vj>的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)值t[i，j]的同時(shí)，還在s[i，j]中記錄了此最優(yōu)三角剖分中與邊（或弦）vi-1vj構(gòu)成的三角形的第三個(gè)頂點(diǎn)的位置。因此，利用最優(yōu)子結(jié)構(gòu)性質(zhì)并借助于s[i，j]，1≤i≤j≤n ，凸（n+l）邊形P=<v0，v1，…，vn>的最優(yōu)三角剖分可容易地在Ο(n)時(shí)間內(nèi)構(gòu)造出來。
習(xí)題：
1、汽車加油問題：
設(shè)有路程長(zhǎng)度為L公里的公路上，分布著m個(gè)加油站，它們的位置分別為p[i]（i=1，2，……，m），而汽車油箱加滿油后（油箱最多可以加油k升），可以行駛n公里。設(shè)計(jì)一個(gè)方案，使汽車經(jīng)過此公路的加油次數(shù)盡量少（汽車出發(fā)時(shí)是加滿油的）。
2、最短路徑：
設(shè)有一個(gè)網(wǎng)絡(luò)，要求從某個(gè)頂點(diǎn)出發(fā)到其他頂點(diǎn)的最短路徑
3、跳馬問題：
在8*8方格的棋盤上，從任意指定的方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。
4、二叉樹的遍歷
5、背包問題
6、用分治法實(shí)現(xiàn)兩個(gè)大整數(shù)相乘
7、設(shè)x1，x2，…，xn是直線上的n個(gè)點(diǎn)，若要用單位長(zhǎng)度的閉區(qū)間去覆蓋這n個(gè)點(diǎn)，至少需要多少個(gè)這樣的單位閉區(qū)間？
8、用關(guān)系“＜”和“＝”將3個(gè)數(shù)A、B和C依次排列時(shí)，有13種不同的序關(guān)系：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要將n個(gè)數(shù)依序進(jìn)行排列，試設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，計(jì)算出有多少鐘不同的序關(guān)系。
9、有一種單人玩的游戲：設(shè)有n(2<=n<=200)堆薄片，各堆順序用0至 n-1編號(hào)，極端情況，有的堆可能沒有薄片。在游戲過程中，一次移動(dòng)只能取某堆上的若干張薄片，移到該堆的相鄰堆上。如指定I堆k張 k 移到I-1(I>0)堆，和將k 張薄片移至I+1(I<n-1)堆。所以當(dāng)有兩個(gè)堆與 I 堆相鄰 時(shí)，I堆原先至少有2k 張薄片；只有一個(gè)堆與 I 堆相鄰 時(shí)， I 堆原先至少有k張薄片。
游戲的目標(biāo)是對(duì)給定的堆數(shù)，和各堆上的薄片數(shù)，按上述規(guī)則移動(dòng)薄片，最終使 各堆的薄片數(shù)相同。為了使移動(dòng)次數(shù)較少些，移動(dòng)哪一堆薄片，和移多少薄片先作以下估算：
設(shè)
ci:I堆的薄片數(shù)(0<=I<n,0<=ci<=200);
v：每堆 的平均薄片數(shù)；
ai:I堆的相鄰堆可以從I堆得到的薄片數(shù)。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
這里并不希望準(zhǔn)確地求出A0 至an-1，而是作以下處理：若令 a0 為0，能按上述算式計(jì)算出 A1至 an-1。程序找出 a 中的最小值，并讓全部a值減去這最小值，使每堆移去的薄片數(shù)大于等于0。
實(shí)際操作采用以下貪心策略：
（1）每次從第一堆出發(fā)順序搜索每一堆，若發(fā)現(xiàn)可從 I堆移走薄片，就完成一次移動(dòng)。即， I堆的相鄰堆從 I堆取走 ai片薄片�？蓮�I 堆移薄片到相鄰堆取于 I堆薄片數(shù)：若I 堆是處于兩端位置( I=0 I=n-1), 要求 ci>=ai ；若 I堆是中間堆，則要求ci>=2ai。
（2）因在ai>0的所有堆中，薄片數(shù)最多的堆 在平分過程中被它的相鄰堆取走的薄片數(shù)也最多。在用策略（1）搜索移動(dòng)時(shí)，當(dāng)發(fā)生沒有滿足條件（1）的可移走薄片的堆時(shí)，采用本策略，讓在ai>0的所有堆中，薄片數(shù)最多的堆被它的相鄰堆取走它的全部薄片。
，我們將會(huì)及時(shí)處理。如轉(zhuǎn)載本網(wǎng)內(nèi)容，請(qǐng)注明出處。