由以上的分析可知，該算法的分割步驟和合并步驟總共耗時O(n)。因此，算法耗費的計算時間T(n)滿足遞歸方程：

    解此遞歸方程可得T(n)=O(nlogn)。

【問題】循環(huán)賽日程表

    問題描述：設(shè)有n=2^k個運動員要進行網(wǎng)球循環(huán)賽�，F(xiàn)要設(shè)計一個滿足以下要求的比賽日程表：

（1）每個選手必須與其他n-1個選手各賽一次；

（2）每個選手一天只能參賽一次；

（3）循環(huán)賽在n-1天內(nèi)結(jié)束。

    請按此要求將比賽日程表設(shè)計成有n行和n-1列的一個表。在表中的第i行，第j列處填入第i個選手在第j天所遇到的選手。其中1≤i≤n，1≤j≤n-1。

    按分治策略，我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進行劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只要讓這兩個選手進行比賽就可以了。

（1）                （2）                           （3）

圖1  2個、4個和8個選手的比賽日程表

    圖1所列出的正方形表（3）是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。

八、動態(tài)規(guī)劃法

       經(jīng)常會遇到復(fù)雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地采用把大問題分解成子問題，并綜合子問題的解導(dǎo)出大問題的解的方法，問題求解耗時會按問題規(guī)模呈冪級數(shù)增加。

       為了節(jié)約重復(fù)求相同子問題的時間，引入一個數(shù)組，不管它們是否對最終解有用，把所有子問題的解存于該數(shù)組中，這就是動態(tài)規(guī)劃法所采用的基本方法。以下先用實例說明動態(tài)規(guī)劃方法的使用。

【問題】       求兩字符序列的最長公共字符子序列

    問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=“x₀，x₁，…，x_m-1”，序列Y=“y₀，y₁，…，y_k-1”是X的子序列，存在X的一個嚴(yán)格遞增下標(biāo)序列<i₀，i₁，…，i_k-1>，使得對所有的j=0，1，…，k-1，有x_ij=y_j。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。

    給定兩個序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。

    如采用列舉A的所有子序列，并一一檢查其是否又是B的子序列，并隨時記錄所發(fā)現(xiàn)的子序列，最終求出最長公共子序列。這種方法因耗時太多而不可取。

    考慮最長公共子序列問題如何分解成子問題，設(shè)A=“a₀，a₁，…，a_m-1”，B=“b₀，b₁，…，b_m-1”，并Z=“z₀，z₁，…，z_k-1”為它們的最長公共子序列。不難證明有以下性質(zhì)：

（1）       如果a_m-1=b_n-1，則z_k-1=a_m-1=b_n-1，且“z₀，z₁，…，z_k-2”是“a₀，a₁，…，a_m-2”和“b₀，b₁，…，b_n-2”的一個最長公共子序列；

（2）       如果a_m-1!=b_n-1，則若z_k-1!=a_m-1，蘊涵“z₀，z₁，…，z_k-1”是“a₀，a₁，…，a_m-2”和“b₀，b₁，…，b_n-1”的一個最長公共子序列；

（3）       如果a_m-1!=b_n-1，則若z_k-1!=b_n-1，蘊涵“z₀，z₁，…，z_k-1”是“a₀，a₁，…，a_m-1”和“b₀，b₁，…，b_n-2”的一個最長公共子序列。

    這樣，在找A和B的公共子序列時，如有a_m-1=b_n-1，則進一步解決一個子問題，找“a₀，a₁，…，a_m-2”和“b₀，b₁，…，b_m-2”的一個最長公共子序列；如果a_m-1!=b_n-1，則要解決兩個子問題，找出“a₀，a₁，…，a_m-2”和“b₀，b₁，…，b_n-1”的一個最長公共子序列和找出“a₀，a₁，…，a_m-1”和“b₀，b₁，…，b_n-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。

    定義c[i][j]為序列“a₀，a₁，…，a_i-2”和“b₀，b₁，…，b_j-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]。

    按此算式可寫出計算兩個序列的最長公共子序列的長度函數(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)造出最長公共子序列。細(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、動態(tài)規(guī)劃的適用條件

    任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。

（1）最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）

    最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(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)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。根據(jù)最優(yōu)化原理導(dǎo)出的動態(tài)規(guī)劃基本方程是解決一切動態(tài)規(guī)劃問題的基本方法。

（2）無后向性

    將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。

（3）子問題的重疊性

    動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。選擇動態(tài)規(guī)劃算法是因為動態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。

    所以，能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征：子問題的重疊性。這個性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。

2、動態(tài)規(guī)劃的基本思想

    前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動態(tài)規(guī)劃是在研究多階段決策問題時推導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。

    動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。

    由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。

    解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最�。┲档慕�。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。

    因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。

3、動態(tài)規(guī)劃算法的基本步驟

    設(shè)計一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法，通�？砂匆韵聨讉�步驟進行：

（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態(tài)規(guī)劃求解。

（2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。

（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。

（4）寫出規(guī)劃方程（包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。

    一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值，但是一般將其改為遞推計算，實現(xiàn)的大體上的框架如下：

    標(biāo)準(zhǔn)動態(tài)規(guī)劃的基本框架

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);                  {狀態(tài)轉(zhuǎn)移方程}

7.            t:=φ(fk+1(xk+1),vk(xk,uk));       {基本方程(9)式}

if  t比fk(xk)更優(yōu) then fk(xk):=t; {計算fk(xk)的最優(yōu)值}

end;

9.  t:=一個極值;                               {∞或－∞}

for 每一個x1∈X1 do

11.     if f1(x1)比t更優(yōu) then t:=f1(x1);       {按照10式求出最優(yōu)指標(biāo)}

12. 輸出t;

    但是，實際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計動態(tài)規(guī)劃，而是按以下幾個步驟進行：

（1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。

（2）遞歸地定義最優(yōu)值。

（3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優(yōu)值。

（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。

    步驟（1）～（3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個最優(yōu)解。

【問題】       凸多邊形的最優(yōu)三角剖分問題

    問題描述：多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內(nèi)的所有點構(gòu)成了多邊形的內(nèi)部；多邊形本身構(gòu)成多邊形的邊界；而平面上其余的點構(gòu)成了多邊形的外部。當(dāng)一個簡單多邊形及其內(nèi)部構(gòu)成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內(nèi)部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內(nèi)部或邊界上。

    通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P=<v₀，v₁，…，v_n-1>表示具有n條邊v₀v₁，v₁v₂，…，v_n-1v_n的一個凸多邊形，其中，約定v₀=v_n 。

    若v_i與v_j是多邊形上不相鄰的兩個頂點，則線段v_iv_j稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形<v_i，v_i+1，…，v_j>和<v_j，v_j+1，…，v_i>。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。圖1是一個凸多邊形的兩個不同的三角剖分。

圖1 一個凸多邊形的2個不同的三角剖分

    在凸多邊形P的一個三角剖分T中，各弦互不相交且弦數(shù)已達(dá)到最大，即P的任一不在T中的弦必與T中某一弦相交。在一個有n個頂點的凸多邊形的三角刮分中，恰好有n-3條弦和n-2個三角形。

    凸多邊形最優(yōu)三角剖分的問題是：給定一個凸多邊形P=<v₀，v₁，…，v_n-1>以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)ω。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應(yīng)的權(quán)即剖分中諸三角形上的權(quán)之和為最小。

    可以定義三角形上各種各樣的權(quán)函數(shù)ω。例如：定義ω(△v_iv_jv_k)=| v_iv_j |+| v_iv_k |+| v_kv_j |，其中，| v_iv_j |是點v_i到v_j的歐氏距離。相應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。

（1）最優(yōu)子結(jié)構(gòu)性質(zhì)

    凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實上，若凸（n+1）邊形P=<v₀，v₁ ，…，v_n>的一個最優(yōu)三角剖分T包含三角形v₀v_kv_n，1≤k≤n-1，則T的權(quán)為3個部分權(quán)的和，即三角形v₀v_kv_n的權(quán)，子多邊形<v₀，v₁，…，v_k>的權(quán)和<v_k，v_k+1，…，v_n>的權(quán)之和�？梢詳嘌杂�T所確定的這兩個子多邊形的三角剖分也是最優(yōu)的，因為若有<v₀，v₁，…，v_k>或<v_k，v_k+1，…，v_n>的更小權(quán)的三角剖分，將會導(dǎo)致T不是最優(yōu)三角剖分的矛盾。

（2）最優(yōu)三角剖分對應(yīng)的權(quán)的遞歸結(jié)構(gòu)

    首先，定義t[i，j]（1≤i<j≤n）為凸子多邊形<v_i-1，v_i，…，v_j>的最優(yōu)三角剖分所對應(yīng)的權(quán)值，即最優(yōu)值。為方便起見，設(shè)退化的多邊形<v_i-1，v_i>具有權(quán)值0。據(jù)此定義，要計算的凸（n+1）邊多邊形P對應(yīng)的權(quán)的最優(yōu)值為t[1，n]。

        t[i，j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計算。由于退化的2頂點多邊形的權(quán)值為0，所以t[i，i]=0，i=1，2，…，n 。當(dāng)j一i≥1時，子多邊形<v_i-1，v_i，…，v_j>至少有3個頂點。由最優(yōu)于結(jié)構(gòu)性質(zhì)，t[i，j]的值應(yīng)為t[i，k]的值加上t[k+1，j]的值，再加上△v_i-1v_kv_j的權(quán)值，并在i≤k≤j-1的范圍內(nèi)取最小。由此，t[i，j]可遞歸地定義為：

（3）計算最優(yōu)值

    下面描述的計算凸（n+1）邊形P=<v₀，v₁，…，v_n>的三角剖分最優(yōu)權(quán)值的動態(tài)規(guī)劃算法MINIMUM_WEIGHT，輸入是凸多邊形P=<v₀，v₁，…，v_n>的權(quán)函數(shù)ω，輸出是最優(yōu)值t[i，j]和使得t[i，k]+t[k+1，j]+ω（△v_i-1v_kv_j）達(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_占用θ(n²)空間，耗時θ(n³)。

（4）構(gòu)造最優(yōu)三角剖分

    如我們所看到的，對于任意的1≤i≤j≤n ，算法MINIMUM_WEIGHT在計算每一個子多邊形<v_i-1，v_i，…，v_j>的最優(yōu)三角剖分所對應(yīng)的權(quán)值t[i，j]的同時，還在s[i，j]中記錄了此最優(yōu)三角剖分中與邊（或弦）v_i-1v_j構(gòu)成的三角形的第三個頂點的位置。因此，利用最優(yōu)子結(jié)構(gòu)性質(zhì)并借助于s[i，j]，1≤i≤j≤n ，凸（n+l）邊形P=<v₀，v₁，…，v_n>的最優(yōu)三角剖分可容易地在Ο(n)時間內(nèi)構(gòu)造出來。

習(xí)題：

1、汽車加油問題：

    設(shè)有路程長度為L公里的公路上，分布著m個加油站，它們的位置分別為p[i]（i=1，2，……，m），而汽車油箱加滿油后（油箱最多可以加油k升），可以行駛n公里。設(shè)計一個方案，使汽車經(jīng)過此公路的加油次數(shù)盡量少（汽車出發(fā)時是加滿油的）。

2、最短路徑：

    設(shè)有一個網(wǎng)絡(luò)，要求從某個頂點出發(fā)到其他頂點的最短路徑

3、跳馬問題：

    在8*8方格的棋盤上，從任意指定的方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。

4、二叉樹的遍歷

5、背包問題

6、用分治法實現(xiàn)兩個大整數(shù)相乘

7、設(shè)x1，x2，…，xn是直線上的n個點，若要用單位長度的閉區(qū)間去覆蓋這n個點，至少需要多少個這樣的單位閉區(qū)間？

8、用關(guān)系“＜”和“＝”將3個數(shù)A、B和C依次排列時，有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個數(shù)依序進行排列，試設(shè)計一個動態(tài)規(guī)劃算法，計算出有多少鐘不同的序關(guān)系。

9、有一種單人玩的游戲：設(shè)有n(2<=n<=200)堆薄片，各堆順序用0至 n-1編號，極端情況，有的堆可能沒有薄片。在游戲過程中，一次移動只能取某堆上的若干張薄片，移到該堆的相鄰堆上。如指定I堆k張 k 移到I-1(I>0)堆，和將k 張薄片移至I+1(I<n-1)堆。所以當(dāng)有兩個堆與 I 堆相鄰 時，I堆原先至少有2k 張薄片；只有一個堆與 I 堆相鄰 時， I 堆原先至少有k張薄片。

       游戲的目標(biāo)是對給定的堆數(shù)，和各堆上的薄片數(shù)，按上述規(guī)則移動薄片，最終使 各堆的薄片數(shù)相同。為了使移動次數(shù)較少些，移動哪一堆薄片，和移多少薄片先作以下估算：

設(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，能按上述算式計算出 A1至 an-1。程序找出 a 中的最小值，并讓全部a值減去這最小值，使每堆移去的薄片數(shù)大于等于0。

實際操作采用以下貪心策略：

（1）每次從第一堆出發(fā)順序搜索每一堆，若發(fā)現(xiàn)可從 I堆移走薄片，就完成一次移動。即， 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)發(fā)生沒有滿足條件（1）的可移走薄片的堆時，采用本策略，讓在ai>0的所有堆中，薄片數(shù)最多的堆被它的相鄰堆取走它的全部薄片。

上一頁  [1] [2] [3] [4] [5] [6]