算法分析總結(jié)

31144遞歸與分治策略 2197271.遞歸 2125832.遞歸函數(shù) 2139963.階乘函數(shù) 3273004.斐波那契數(shù)列 3131445.整數(shù)劃分 3217216.分治法 4166867.大整數(shù)的乘法 5324048.矩陣乘 682869.合并排序 71881210.棋盤覆蓋 8342511.循環(huán)賽日程表 899512.快速排序 9664713.貪心算法 92723414.貪心算法基本要素 973815.活動安排問題 10589916.0-1背包問題與背包問題 1142900-1背包問題 11213660-1背包問題改進(jìn)算法 111753117.最優(yōu)裝載 111125918.單源最短路徑 122150719.Dijkstra算法 132195820.最小生成樹 132524221.多機(jī)調(diào)度算法 171810722.備忘錄方法 173063824.凸多邊形最優(yōu)三角剖分 18543825.長公共子序列 19460926.多邊性游戲 201006627.二分搜索技術(shù) 21遞歸與分治策略遞歸遞歸，就是在運(yùn)行的過程中調(diào)用自己。構(gòu)成遞歸需具備的條件：函數(shù)嵌套調(diào)用過程示例1.子問題須與原始問題為同樣的事，且更為簡單；2.不能無限制地調(diào)用本身，須有個(gè)出口，化簡為非遞歸狀況處理。在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，并規(guī)定其他所有情況都能被還原為其基本情況。例如，下列為某人祖先的遞歸定義：某人的雙親是他的祖先（基本情況）。某人祖先的雙親同樣是某人的祖先（遞歸步驟）。斐波納契數(shù)列（FibonacciSequence），又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21I[1]

斐波納契數(shù)列是典型的遞歸案例：遞歸函數(shù)遞歸方法——漢諾塔3.階乘函數(shù)下面是求10的階乘，你參考下：

voidmain

{

intfn=1，i=1;

intn=10;

//下面就是求10的階乘

for(i=1;i<=n;i++)

{

fn=fn*i;

}

printf("10的階乘是%d",fn);

}斐波那契數(shù)列即定義兩個(gè)數(shù)字，后面的數(shù)字是前兩個(gè)數(shù)字之和a1=1，a2=1，a3=2，an=an-1+an-2(n>=3)斐波那契數(shù)列很有趣，每一個(gè)數(shù)都是整型數(shù)，可是它的通項(xiàng)公式卻由無理數(shù)進(jìn)行表達(dá)。斐波那契數(shù)列的通用表達(dá)是：第一個(gè)數(shù)和第二個(gè)數(shù)是1，從第三個(gè)數(shù)開始，每一個(gè)數(shù)都是它的前兩個(gè)數(shù)的和。a1=1，a2=1，a3=2，an=an-1+an-2(n>=3),用C言代碼可以實(shí)現(xiàn)第幾個(gè)斐波那契數(shù)。整數(shù)劃分◎根據(jù)n和m的關(guān)系，考慮以下幾種情況：其中n為要劃分的正整數(shù)，m是劃分中的最大加數(shù)

1.當(dāng)n=1時(shí)，不論m的值為多少（m>0)，只有一種劃分即{1};

2.當(dāng)m=1時(shí)，不論n的值為多少，只有一種劃分即n個(gè)1，{1,1,1,...,1};

3.當(dāng)n=m時(shí)，根據(jù)劃分中是否包含n，可以分為兩種情況：

(1)劃分中包含n的情況，只有一個(gè)即{n}；

(2)劃分中不包含n的情況，這時(shí)劃分中最大的數(shù)字也一定比n小，即n的所有(n-1)劃分。因此f(n,n)=1+f(n,n-1);

4.當(dāng)n<m時(shí)，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n);

5.但n>m時(shí)，根據(jù)劃分中是否包含最大值m，可以分為兩種情況：

(1)劃分中包含m的情況，即{m,{x1,x2,...xi}},其中{x1,x2,...xi}的和為n-m，可能再次出現(xiàn)m，因此是（n-m）的m劃分，因此這種劃分個(gè)數(shù)為f(n-m,m);

(2)劃分中不包含m的情況，則劃分中所有值都比m小，即n的(m-1)劃分，個(gè)數(shù)為f(n,m-1);因此f(n,m)=f(n-m,m)+f(n,m-1);

綜合以上情況，我們可以看出，上面的結(jié)論具有遞歸定義特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，將會轉(zhuǎn)換為情況（5）。而情況（5）為通用情況，屬于遞推的方法，其本質(zhì)主要是通過減小m以達(dá)到回歸條件，從而解決問題。其遞推表達(dá)式如下：f(n,m)=1;(n=1orm=1)f(n,m)=f(n,n);(n<m)1+f(n,m-1);(n=m)f(n-m,m)+f(n,m-1);(n>m)分治法分治法在每一層遞歸上都有三個(gè)步驟：分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題；合并：將各個(gè)子問題的解合并為原問題的解。分治策略的例子：合并排序，快速排序，折半查找，二叉遍歷樹及其相關(guān)特性。大整數(shù)的乘法設(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積XY。我們可以用小學(xué)所學(xué)的方法來設(shè)計(jì)一個(gè)計(jì)算乘積XY的算法，但是這樣做計(jì)算步驟太多，顯得效率較低。如果將每2個(gè)1位數(shù)的乘法或加法看作一步運(yùn)算，那么這種方法要作O(n2)步運(yùn)算才能求出乘積XY。下面我們用分治法來設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。x=|A|B|

y=|C|D|圖6-3大整數(shù)X和Y的分段我們將n位的二進(jìn)制整數(shù)X和Y各分為2段，每段的長為n/2位(為簡單起見，假設(shè)n是2的冪)，如圖6-3所示。由此，X=A2n/2+B，Y=C2n/2+D。這樣，X和Y的乘積為：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD

(1)如果按式(1)計(jì)算XY，則我們必須進(jìn)行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，

以及3次不超過n位的整數(shù)加法(分別對應(yīng)于式(1)中的加號)，此外還要做2次移位(分別對應(yīng)于式(1)中乘2n和乘2n/2)。所有這些加法和移位共用O(n)步運(yùn)算。設(shè)T(n)是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則由式(1)，我們有:T(1)=1T(n)=4T(n/2)+O(n)

(2)由此可得T(n)=O(n2)。因此，用(1)式來計(jì)算X和Y的乘積并不比小學(xué)生的方法更有效。要想改進(jìn)算法的計(jì)算復(fù)雜性，必須減少乘法次數(shù)。為此我們把XY寫成另一種形式:XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD

(3)雖然，式(3)看起來比式(1)復(fù)雜些，但它僅需做3次n/2位整數(shù)的乘法(AC，BD和(A-B)(D-C))，6次加、減法和2次移位。由此可得:T(1)=1T(n)=3T(n/2)+cn

(4)用解遞歸方程的套用公式法馬上可得其解為T(n)=O(nlog3)=O(n1.59)。利用式(3)，并考慮到X和Y的符號對結(jié)果的影響，我們給出大整數(shù)相乘的完整算法MULT如下:functionMULT(X，Y，n);{X和Y為2個(gè)小于2n的整數(shù)，返回結(jié)果為X和Y的乘積XY}矩陣乘分治策略將2個(gè)二階矩陣采用下列方式來計(jì)算：

其中：

數(shù)一下，這樣來計(jì)算2個(gè)二階矩陣的乘法用了7次乘法，18次加法。而蠻力法用了8次乘法和4次加法。當(dāng)然，這還不能體現(xiàn)出它的優(yōu)越性，它的優(yōu)越性表現(xiàn)在當(dāng)矩陣的階趨于無窮大時(shí)的漸進(jìn)效率。

由上面的式子，根據(jù)矩陣的相關(guān)知識，對于分塊矩陣，也可以寫成上述形式：

9.合并排序棋盤覆蓋11.循環(huán)賽日程表算法思路：按分治策略，我們可以將所有的選手分為兩半，則n個(gè)選手的比賽日程表可以通過n/2個(gè)選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。如上圖，所列出的正方形表是8個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個(gè)比賽日程表推廣到具有任意多個(gè)選手的情形。12.快速排序貪心算法貪婪算法可解決的問題通常大部分都有如下的特性：⑴隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過并被選出的候選對象，另一個(gè)包含已經(jīng)被考慮過但被丟棄的候選對象。⑵有一個(gè)函數(shù)來檢查一個(gè)候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。⑶還有一個(gè)函數(shù)檢查是否一個(gè)候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性。⑷選擇函數(shù)可以指出哪一個(gè)剩余的候選對象最有希望構(gòu)成問題的解。⑸最后，目標(biāo)函數(shù)給出解的值。⑹為了解決問題，需要尋找一個(gè)構(gòu)成解的候選對象集合，它可以優(yōu)化目標(biāo)函數(shù)，貪婪算法一步一步的進(jìn)行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行，那么該對象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個(gè)解通常是最優(yōu)的。貪心算法基本要素貪心算法的基本要素：1.貪心選擇性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2.當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。貪心算法的基本思路：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問題：1.不能保證求得的最后解是最佳的；2.不能用來求最大或最小解問題；3.只能求滿足某些約束條件的可行解的范圍。實(shí)現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；由所有解元素組合成問題的一個(gè)可行解；貪心算法思想：顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。15.活動安排問題問題描述:

設(shè)有n個(gè)活動的集合E={1,2,…,n}，其中每個(gè)活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動i，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交,則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。16.0-1背包問題與背包問題0-1背包問題0-1背包問題改進(jìn)算法最優(yōu)裝載問題描述:

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。

編程任務(wù)：對于給定的n個(gè)集裝箱和輪船的載重量C，編程計(jì)算裝入最多時(shí)的集裝箱個(gè)數(shù)。

輸入:

輸入由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)輸入的第1行中有2個(gè)正整數(shù)n和C。正整數(shù)n是集裝箱個(gè)數(shù)；正整數(shù)C是輪船的載重量。接下來的一行中有n個(gè)整數(shù)，分別表示n個(gè)集裝箱的重量，它們之間用空格分隔。其中1<=n<=2000，所有正整數(shù)不超過231-1

輸出:

對應(yīng)每組輸入，輸出的每行是計(jì)算出的裝入最多時(shí)的集裝箱個(gè)數(shù)。

樣例輸入:

45

3521

樣例輸出:

2解決：貪心算法入門題，其實(shí)代碼可以很短的，就是選擇最小的裝在里邊就行了，但是還是練習(xí)下記錄哪個(gè)裝入為好18.單源最短路徑Dijkstra算法1.dijkstra算法簡介Dijkstra算法是由E.W.Dijkstra于1959年提出，又叫迪杰斯特拉算法，它應(yīng)用了貪心算法模式，是目前公認(rèn)的最好的求解最短路徑的方法。算法解決的是有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題，其主要特點(diǎn)是每次迭代時(shí)選擇的下一個(gè)頂點(diǎn)是標(biāo)記點(diǎn)之外距離源點(diǎn)最近的頂點(diǎn)。但由于dijkstra算法主要計(jì)算從源點(diǎn)到其他所有點(diǎn)的最短路徑，所以算法的效率較低。2.dijkstra算法基本過程假設(shè)路網(wǎng)中每一個(gè)節(jié)點(diǎn)都有標(biāo)號

是從出發(fā)點(diǎn)s到點(diǎn)t的最短路徑長度；表示從s到t的最短路徑中t點(diǎn)的前一個(gè)點(diǎn)。求解從出發(fā)點(diǎn)s到點(diǎn)t的最短路徑算法的基本過程為：1.

初始化。出發(fā)點(diǎn)設(shè)置為：

標(biāo)記起源點(diǎn)s，記k=s,其他所有點(diǎn)設(shè)為未標(biāo)記。2.

檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其他直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置:3.

選取下一個(gè)點(diǎn)。從所有未標(biāo)記的點(diǎn)中選取最小的點(diǎn)i，點(diǎn)i被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。4.

找到點(diǎn)i的前一點(diǎn)。從已經(jīng)標(biāo)記的點(diǎn)集合中找到直接連接到點(diǎn)i的點(diǎn),并標(biāo)記為。5.

標(biāo)記點(diǎn)i。如果所有的點(diǎn)已標(biāo)記，則算法結(jié)束。否則，記k=i，轉(zhuǎn)到2繼續(xù)。從以上算法的步驟中可以看出：dijkstra算法的關(guān)鍵部分是從未標(biāo)記的點(diǎn)中不斷地找出距離源點(diǎn)距離最近的點(diǎn)，并把改點(diǎn)加入到標(biāo)記的點(diǎn)集合中，同時(shí)更新未標(biāo)記的點(diǎn)集合中其余點(diǎn)到起始點(diǎn)的最短估計(jì)距離[z1]

。最小生成樹Prim任選一個(gè)定點(diǎn)，以該頂點(diǎn)為基礎(chǔ)，選出離他最近的一個(gè)點(diǎn)，然后就是距這兩個(gè)定點(diǎn)最近的一個(gè)點(diǎn)。以此類推，直到所有點(diǎn)都遍歷一次。此為原始的加權(quán)連通圖。每條邊一側(cè)的數(shù)字代表其權(quán)值。頂點(diǎn)D被任意選為起始點(diǎn)。頂點(diǎn)A、B、E和F通過單條邊與D相連。A是距離D最近的頂點(diǎn)，因此將A及對應(yīng)邊AD以高亮表示。C,GA,B,E,FD

下一個(gè)頂點(diǎn)為距離D或A最近的頂點(diǎn)。B距D為9，距A為7，E為15，F(xiàn)為6。因此，F(xiàn)距D或A最近，因此將頂點(diǎn)F與相應(yīng)邊DF以高亮表示。C,GB,E,FA,D算法繼續(xù)重復(fù)上面的步驟。距離A為7的頂點(diǎn)B被高亮表示。CB,E,GA,D,F

在當(dāng)前情況下，可以在C、E與G間進(jìn)行選擇。C距B為8，E距B為7，G距F為11。E最近，因此將頂點(diǎn)E與相應(yīng)邊BE高亮表示。無C,E,GA,D,F,B

這里，可供選擇的頂點(diǎn)只有C和G。C距E為5，G距E為9，故選取C，并與邊EC一同高亮表示。無C,GA,D,F,B,E頂點(diǎn)G是唯一剩下的頂點(diǎn)，它距F為11，距E為9，E最近，故高亮表示G及相應(yīng)邊EG。無GA,D,F,B,E,C現(xiàn)在，所有頂點(diǎn)均已被選取，圖中綠色部分即為連通圖的最小生成樹。在此例中，最小生成樹的權(quán)值之和為39。無無A,D,F,B,E,C,GKruskal圖例描述：首先第一步，我們有一張圖Graph，有若干點(diǎn)和邊

將所有的邊的長度排序，用排序的結(jié)果作為我們選擇邊的依據(jù)。這里再次體現(xiàn)了貪心算法的思想。資源排序，對局部最優(yōu)的資源進(jìn)行選擇，排序完成后，我們率先選擇了邊AD。這樣我們的圖就變成了右圖在剩下的變中尋找。我們找到了CE。這里邊的權(quán)重也是5依次類推我們找到了6,7,7，即DF，AB，BE。下面繼續(xù)選擇，BC或者EF盡管現(xiàn)在長度為8的邊是最小的未選擇的邊。但是現(xiàn)在他們已經(jīng)連通了（對于BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以不需要選擇他們。類似的BD也已經(jīng)連通了（這里上圖的連通線用紅色表示了）。最后就剩下EG和FG了。當(dāng)然我們選擇了EG。最后成功的圖就是右：21.多機(jī)調(diào)度算法◎處理時(shí)間最長的作業(yè)分配給最先空閑的機(jī)器采用最長處理時(shí)間作業(yè)優(yōu)先的貪心算則策略設(shè)計(jì)出解多機(jī)調(diào)度問題的較好的近似算法。1.當(dāng)n<=m時(shí)，只要將作業(yè)時(shí)間區(qū)間分配給作業(yè)即可。時(shí)間為最長時(shí)間的作業(yè)。2.當(dāng)n>m時(shí)，首先將n個(gè)作業(yè)從大到小排序。然后依此順序分步將作業(yè)分配給空閑的處理機(jī)，每步分配給一個(gè)機(jī)器，而且需要考慮分配哪一個(gè)作業(yè)。根據(jù)這種思想可利用如下貪心原則:從剩下的作業(yè)中，選擇需要處理時(shí)間最長。然后依次選擇處理時(shí)間次長的作業(yè)，直到所有的作業(yè)全部處理完畢，或者機(jī)器不能再處理其他作業(yè)。備忘錄方法動態(tài)規(guī)劃算法的一個(gè)變形是備忘錄方法。備忘錄方法也用一個(gè)表格來保存已解決的子問題的答案，在下次需要解決此問題時(shí)，只要簡單地查看該子問題的解答，而不必重新計(jì)算。與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。

備忘錄方法為每個(gè)子問題建立了一個(gè)記錄項(xiàng)，初始化時(shí)，該記錄項(xiàng)存入一個(gè)特殊的值，表示該子問題尚未求解。在求解過程中，對每個(gè)待求的子問題，首先查看相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中存儲的是初始化時(shí)存入的特殊值，則表示該子問題是第一次遇到，則此時(shí)計(jì)算出該子問題的解，并保存在相應(yīng)的記錄項(xiàng)中。若記錄項(xiàng)中存儲的已不是初始化時(shí)存入的特殊值，則表示該問題已被計(jì)算過，其相應(yīng)的記錄項(xiàng)中存儲的是該子問題的解答。此時(shí)，只要從記錄項(xiàng)中取出該子問題的解答即可。

一般來講，當(dāng)一個(gè)問題的所有子問題至少要解一次時(shí)，則用動態(tài)規(guī)劃算法比用備忘錄算法好。此時(shí)，動態(tài)規(guī)劃算法沒有任何多余的計(jì)算，還可利用其規(guī)則的表格存取方式，來減少在動態(tài)規(guī)劃算法中的計(jì)算時(shí)間和空間需求。當(dāng)子問題空間中部分子問題可不必求解時(shí)，用備忘錄方法則較有利，因?yàn)閺钠淇刂平Y(jié)構(gòu)可以看出，該方法只解那些確實(shí)需要求解的子問題。凸多邊形最優(yōu)三角剖分題目描述：用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊的凸多邊形。

給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。解題思路：若凸(n+1)邊形P={v0,v1,…,vn-1}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和。可以斷言，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衶v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。那么我們定義一個(gè)t[i][j]，1<=i<=j<=N,為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。據(jù)此定義，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t[1][n]。t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i≥1時(shí)，凸子多邊形至少有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。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使t[i][j]值達(dá)到最小的位置。由此，t[i][j]可遞歸地定義為：對于要求的t[1][n]，可以用通過由下至上的，從鏈長（多邊形的邊）為2開始計(jì)算，每次求t[i][j]的最小值，并且記錄最小值所對應(yīng)的K值，根據(jù)最優(yōu)子結(jié)構(gòu)的性質(zhì)，逐步向上就可以求出t[1][n]的最小值。類似的，求三角劃分頂點(diǎn)的乘積的最小值問題，也是一樣的。25.長公共子序列問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列?？紤]最長公共子序列問題如何分解成子問題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質(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è)最長公共子序列；（2）如果am-1!=bn-1，則若zk-1!=am-1，蘊(yùn)涵“z0，z1，…，zk-1”是