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