2.5 動(dòng)態(tài)規(guī)劃法

2.5.1 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

動(dòng)態(tài)規(guī)劃法（dynamicprogramming）也是將待求解問題分解成若干個(gè)子問題，但是子問題之間往往不是相互獨(dú)立的，如果用分治法求解，這些子問題的重疊部分被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃法將每個(gè)子問題求解一次并將其解保存在一個(gè)表格（通常采用數(shù)組）中，當(dāng)需要再次解此子問題時(shí)，只是簡單地通過查表獲得該子問題的解，從而避免了大量重復(fù)計(jì)算。動(dòng)態(tài)規(guī)劃法的一般過程如圖2-6所示。

圖2-6 動(dòng)態(tài)規(guī)劃法的求解過程

例如，F(xiàn)ibonacci數(shù)列存在如下遞推關(guān)系式：

注意到計(jì)算F（n）是以計(jì)算它的兩個(gè)重疊子問題F（n-1）和F（n-2）的形式來表達(dá)的，可以利用一維數(shù)組fib[n+1]填入F（n）的值（補(bǔ)充定義F（0）=0），開始時(shí)，根據(jù)遞推式的初始條件可以直接填入0和1，然后根據(jù)遞推式填寫其他元素，如圖2-7所示。顯然，數(shù)組中最后一項(xiàng)就是F（n）的值。

圖2-7 動(dòng)態(tài)規(guī)劃法求解Fibonacci數(shù)列的填表過程

一般來說，動(dòng)態(tài)規(guī)劃法的求解過程由以下三個(gè)階段組成。

（1）劃分子問題：將原問題分解為若干個(gè)子問題，并且子問題之間具有重疊關(guān)系；

（2）動(dòng)態(tài)規(guī)劃函數(shù)：根據(jù)子問題之間的重疊關(guān)系找到子問題滿足的遞推關(guān)系式（稱為動(dòng)態(tài)規(guī)劃函數(shù)）；

（3）填寫表格：設(shè)計(jì)表格的形式及內(nèi)容，根據(jù)遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。

顯然，動(dòng)態(tài)規(guī)劃法的關(guān)鍵是找到體現(xiàn)子問題之間重疊關(guān)系的動(dòng)態(tài)規(guī)劃函數(shù)。在本書中，F(xiàn)LOYD算法是利用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)的一個(gè)高效算法。

2.5.2 算法設(shè)計(jì)實(shí)例——數(shù)塔問題

【問題】 如圖2-8所示的一個(gè)數(shù)塔，從數(shù)塔的頂層出發(fā)，在每一個(gè)結(jié)點(diǎn)可以選擇向左走或向右走，一直走到底層，要求找出一條路徑，使得路徑上的數(shù)值和最大。例如，圖2-8所示數(shù)塔的最大數(shù)值和是：8+15+9+10+18=60。

圖2-8 一個(gè)5層數(shù)塔

【想法】 觀察圖2-8所示數(shù)塔不難發(fā)現(xiàn)，從5層數(shù)塔的頂層（設(shè)頂層為第1層）出發(fā)，下一層選擇向左走還是向右走取決于兩個(gè)4層數(shù)塔的最大數(shù)值和，如圖2-10所示，顯然，子問題具有重疊的特征。

圖2-10 數(shù)塔問題的子問題具有重疊關(guān)系

如何找到子問題滿足的動(dòng)態(tài)規(guī)劃函數(shù)呢？顯然，動(dòng)態(tài)規(guī)劃的求解需要從底層開始進(jìn)行決策，決策過程如圖2-11所示。底層的每個(gè)數(shù)字可以看做1層數(shù)塔，則最大數(shù)值和就是其自身，填寫圖2-11的最下一行；第4層的決策是在最底層決策的基礎(chǔ)上進(jìn)行求解的，可以看做4個(gè)2層數(shù)塔，如圖2-12（a）所示，對(duì)每個(gè)數(shù)塔進(jìn)行求解，填寫圖2-11的第4行；第3層的決策是在第4層決策的基礎(chǔ)上進(jìn)行求解的，可以看做3個(gè)2層的數(shù)塔，如圖2-12（b）所示，對(duì)每個(gè)數(shù)塔進(jìn)行求解，填寫圖2-11的第3行……最后第1層的決策結(jié)果就是數(shù)塔問題的整體最優(yōu)解。

圖2-11 數(shù)塔問題的決策過程

圖2-12 數(shù)塔問題的動(dòng)態(tài)規(guī)劃求解過程

由上述填表過程，可以設(shè)計(jì)數(shù)塔問題的存儲(chǔ)結(jié)構(gòu)。將給定的數(shù)塔存儲(chǔ)為如圖2-9所示的下三角矩陣d[n][n]，設(shè)二維數(shù)組maxAdd[n][n]存儲(chǔ)動(dòng)態(tài)規(guī)劃每一步的決策結(jié)果，最后maxAdd[0][0]存儲(chǔ)的就是數(shù)塔問題的解，則得到如下動(dòng)態(tài)規(guī)劃函數(shù)：

圖2-9 數(shù)塔的存儲(chǔ)

為了求得最大數(shù)值和的路徑，設(shè)數(shù)組path[n][n]保存每一次決策所選擇的數(shù)字在數(shù)組d[n][n]中的列下標(biāo)，例如，path[i][j]的值表示在第i層第j個(gè)數(shù)塔的決策時(shí)所選擇的路徑，path[i][j]的值定義如下：

【算法】 設(shè)函數(shù)DataTower完成n層數(shù)塔問題并輸出對(duì)應(yīng)的路徑，算法用偽代碼描述如下：

            for（j=0；j＜n；j++）
              maxAdd[n-1][j]=d[n-1][j]；

【程序】 主函數(shù)首先初始化數(shù)組d[n][n]為n層數(shù)塔的數(shù)字，然后調(diào)用函數(shù)DataTorwer求解最大數(shù)值和并輸出相應(yīng)的路徑。程序如下：

            #include＜stdio.h＞                        //使用庫函數(shù)printf
            constintn=5；                              //假設(shè)數(shù)塔是5層
            intDataTorwer（intd[n][n]）；              //函數(shù)聲明，求解n層數(shù)塔
                                                       //以下是主函數(shù)
            intmain（）
            {
              intd[n][n]={{8}，{12，15}，{3，9，6}，{8，10，5，12}，{16，4，18，10，9}}；
              printf（＂最大數(shù)值和為：%d\n＂，DataTorwer（d））； //輸出最大數(shù)值和
              return0；                                //將0返回操作系統(tǒng)，表明程序正常結(jié)束
            }
                                                       //以下是其他函數(shù)定義
            intDataTorwer（intd[n][n]）                //求解數(shù)塔問題，數(shù)塔存儲(chǔ)在數(shù)組d[n][n]中
            {
              intmaxAdd[n][n]={0}，path[n][n]={0}；    //初始化
              inti，j；

              for（j=0；j＜n；j++）                    //初始化底層決策結(jié)果
                  maxAdd[n-1][j]=d[n-1][j]；
              for（i=n-2；i＞=0；i--）                 //進(jìn)行第i層的決策
                  for（j=0；j＜=i；j++）               //填寫addMax[i][j]，只填寫下三角
                    if（maxAdd[i+1][j]＞maxAdd[i+1][j+1]）
                    {
                      maxAdd[i][j]=d[i][j]+maxAdd[i+1][j]；
                      path[i][j]=j；                   //本次決策選擇下標(biāo)j的元素
                    }
                    else
                    {
                      maxAdd[i][j]=d[i][j]+maxAdd[i+1][j+1]；
                      path[i][j]=j+1；                 //本次決策選擇下標(biāo)j+1的元素
                    }
              printf（＂路徑為：%d＂，d[0][0]）；      //輸出頂層數(shù)字
              j=path[0][0]；   //頂層決策是選擇下一層列下標(biāo)為path[0][0]的元素
              for（i=1；i＜n；i++）
              {
                  printf（＂--＞%d＂，d[i][j]）；
                  j=path[i][j]；                       //本層決策是選擇下一層列下標(biāo)為path[i][j]的元素
              }
              returnmaxAdd[0][0]；                     //返回最大數(shù)值和，即最終的決策結(jié)果
            }