動態(tài)規(guī)劃

動態(tài)規(guī)劃（Dynamic Programming）是解決多階段決策問題常用的最優(yōu)化理論埃疫，動態(tài)規(guī)劃和分治法一樣剂买，也是通過定義子問題气笙，先求解子問題，然后在由子問題的解組合出原問題的解梁剔。但是它們之間的不同點是分治法的子問題之間是相互獨立的，而動態(tài)規(guī)劃的子問題之間存在堆疊關(guān)系（遞推關(guān)系式確定的遞推關(guān)系）舞蔽。動態(tài)規(guī)劃方法的原理就是把多階段決策過程轉(zhuǎn)化為一系列的單階段決策問題荣病，利用各個階段之間的遞推關(guān)系，逐個確定每個階段的最優(yōu)化決策渗柿，最終堆疊出多階段決策的最優(yōu)化決策結(jié)果个盆。動態(tài)規(guī)劃問題有很多模型，常見的有線性模型朵栖、（字符或數(shù)字）串模型砾省、區(qū)間模型、狀態(tài)壓縮模型混槐，等等，本節(jié)課后面介紹的最長公共子序列問題轩性，就是一個典型的串模型声登。

動態(tài)規(guī)劃適合求解多階段（狀態(tài)轉(zhuǎn)換）決策問題的最優(yōu)解，也可用于含有線性或非線性遞推關(guān)系的最優(yōu)解問題揣苏，但是這些問題都必須滿足最優(yōu)化原理和子問題的“無后向性”悯嗓。

最優(yōu)化原理：

最優(yōu)化原理其實就是問題的最優(yōu)子結(jié)構(gòu)的性質(zhì)，如果一個問題的最優(yōu)子結(jié)構(gòu)是不論過去狀態(tài)和決策如何卸察，對前面的決策所形成的狀態(tài)而言脯厨，其后的決策必須構(gòu)成最優(yōu)策略。也就是說坑质，不管之前的決策是否是最優(yōu)決策合武，都必須保證從現(xiàn)在開始的決策是在之前決策基礎(chǔ)上的最優(yōu)決策，則這樣的最優(yōu)子結(jié)構(gòu)就符合最優(yōu)化原理涡扼。

無后向性（無后效性）：

所謂“無后向性”稼跳，就是當(dāng)各個階段的子問題確定以后，對于某個特定階段的子問題來說吃沪，它之前各個階段的子問題的決策只影響該階段的決策汤善，對該階段之后的決策不產(chǎn)生影響.對于某一個狀態(tài) S 來說，只要 S 狀態(tài)確定了以后票彪，S 以后的那些依靠 S 狀態(tài)做最優(yōu)選擇的狀態(tài)也就都確定了红淡，S 之后的狀態(tài)只受 S 狀態(tài)的影響。也就是說降铸，無論之前是經(jīng)過何種決策途徑來到了 S 狀態(tài)在旱，S 狀態(tài)確定以后，其后續(xù)狀態(tài)的演化結(jié)果都是一樣的垮耳，不會因為到達(dá) S 狀態(tài)的決策路徑的不同而產(chǎn)生不同的結(jié)果颈渊，這就是無后向性遂黍。

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

和分治法一樣，動態(tài)規(guī)劃解決復(fù)雜問題的思路也是先對問題進(jìn)行分解俊嗽，然后通過求解小規(guī)模的子問題再反推出原問題的結(jié)果雾家。但是動態(tài)規(guī)劃分解子問題不是簡單地按照“大事化小”的方式進(jìn)行的，而是沿著決策的階段來劃分子問題绍豁，決策的階段可以隨時間劃分芯咧，也可以隨著問題的演化狀態(tài)來劃分。分治法要求子問題是互相獨立的竹揍，以便分別求解并最終合并出原始問題的解敬飒。分治法對所有的子問題都“一視同仁”地進(jìn)行計算求解，如果分解的子問題中存在相同子問題芬位，就會存在重復(fù)求解子問題的情況无拗。

比如某個問題 A，第一次分解為 A1 和 A2 兩個子問題昧碉，A1 又可分解為 A11 和 A12 兩個子問題英染，A2 又分解為 A21 和 A22 兩個子問題，分治法會分別求解 A11被饿、A12四康、A21 和 A22 四個子問題，即便 A12 和 A21 是相同的子問題狭握，分治法也依然會計算四次子問題的解闪金，這就存在重復(fù)計算的問題，重復(fù)計算相同的子問題會影響求解的效率论颅。

與之相反哎垦，動態(tài)規(guī)劃法的子問題不是互相獨立的，子問題之間通常有包含關(guān)系恃疯，甚至兩個子問題可以包含相同的子子問題撼泛。比如，子問題 A 的解可能由子問題 C 的解遞推得到澡谭，同時愿题，子問題 B 的解也可能由子問題 C 的解遞推得到。對于這種情況蛙奖，動態(tài)規(guī)劃法對子問題 C 只求解一次潘酗，然后將其結(jié)果保存在一張表中（此表也被稱為備忘錄）。當(dāng)求解子問題 A 或子問題 B 的時候雁仲，如果發(fā)現(xiàn)子問題 C 已經(jīng)求解過（在備忘錄表中能查到）仔夺，則不再求解子問題 C，而是直接使用從表中查到的子問題 C 的解攒砖，避免了子問題 C 被重復(fù)計算求解的問題缸兔。

動態(tài)規(guī)劃法不像貪婪法或分治法那樣有固定的算法實現(xiàn)模式日裙，線性規(guī)劃問題和區(qū)間動態(tài)規(guī)劃問題的實現(xiàn)方法就完全不同。作為解決多階段決策最優(yōu)化問題的一種思想惰蜜，可以用帶備忘錄的窮舉方法實現(xiàn)昂拂，也可以根據(jù)堆疊子問題之間的遞推公式用遞推的方法實現(xiàn)。但是從算法設(shè)計的角度分析抛猖，使用動態(tài)規(guī)劃法一般需要四個步驟格侯，分別是：

1. 定義最優(yōu)子問題（最優(yōu)解的子結(jié)構(gòu)）
2. 定義狀態(tài)（最優(yōu)解的值）
3. 定義決策和狀態(tài)轉(zhuǎn)換方程（定義計算最優(yōu)解的值的方法）
4. 確定邊界條件

這四個問題解決了，算法也就確定了财著。接下來就結(jié)合兩個實例分別介紹這四個步驟联四，這兩個例子分別是經(jīng)典的 0-1 背包問題和最長公共子序列問題。

定義最優(yōu)子問題

定義最優(yōu)子問題撑教，也就是最優(yōu)解的子結(jié)構(gòu)朝墩，它確定問題的優(yōu)化目標(biāo)以及如何決策最優(yōu)解，并對決策過程劃分階段伟姐。所謂階段鱼辙，可以理解為一個問題從開始到解決需要經(jīng)過的環(huán)節(jié)，這些環(huán)節(jié)前后關(guān)聯(lián)玫镐。

對于 0-1 背包問題，每選擇裝一個物品可以看做是一個階段怠噪，其子問題就可以定義為每次向包中裝（選擇）一個物品恐似，直到超過背包的最大容量為止。
最長公共子序列問題可以按照問題的演化狀態(tài)劃分階段傍念，這就需要先定義狀態(tài)矫夷，有了狀態(tài)的定義，只要狀態(tài)發(fā)生了變化憋槐，就可以認(rèn)為是一個階段双藕。

定義狀態(tài)

狀態(tài)既是決策的對象，也是決策的結(jié)果阳仔，對于每個階段來說忧陪，對起始狀態(tài)施加決策，使得狀態(tài)發(fā)生改變近范，得到?jīng)Q策的結(jié)果狀態(tài)嘶摊。初始狀態(tài)經(jīng)過每一個階段的決策（狀態(tài)改變）之后，最終得到的狀態(tài)就是問題的解评矩。當(dāng)然叶堆，不是所有的決策序列施加于初始狀態(tài)后都可以得到最優(yōu)解，只有一個決策序列能得到最優(yōu)解斥杜。狀態(tài)的定義是建立在子問題定義基礎(chǔ)之上的虱颗，因此狀態(tài)必須滿足無后向性要求沥匈。必要時，可以增加狀態(tài)的維度忘渔，引入更多的約束條件高帖，使得狀態(tài)定義滿足無后向性要求。

0-1 背包問題本身是個線性過程辨萍，但是如果簡單將狀態(tài)定義為裝入的物品編號棋恼，也就是定義 s[i] 為裝入第 i 件物品后獲得的最大價值，則子問題無法滿足無后向性要求锈玉，原因是之前的任何一個決策都會影響到所有的后序決策（因為裝入物品后背包容量發(fā)生變化了）爪飘，因此需要增加一個維度的約束。

考慮到每裝入一個物品拉背，背包的剩余容量就會減少师崎，故而選擇將背包容量也包含在狀態(tài)定義中。最終背包問題的狀態(tài) s[i,j] 定義為將第 i 件物品裝入容量為 j 的背包中所能獲得的最大價值椅棺。對于最長公共子序列問題犁罩，如果定義 str1[1…i] 為第一個字符串前 i 個字符組成的子串，定義 >str2[1…j] 為第二個字符串的前 j 個字符組成的子串两疚，則最長公共子序列問題的狀態(tài) s[i,j] 定義為 str1[1…i] 與 str2[1…j] 的最長公共子序列長度床估。

定義決策和狀態(tài)轉(zhuǎn)換方程

決策就是能使?fàn)顟B(tài)發(fā)生轉(zhuǎn)變的選擇動作，如果選擇動作有多個诱渤，則決策就是取其中能使得階段結(jié)果最優(yōu)的那一個丐巫。狀態(tài)轉(zhuǎn)換方程是描述狀態(tài)轉(zhuǎn)換關(guān)系的一系列等式，也就是從 n-1 階段到 n 階段演化的規(guī)律勺美。狀態(tài)轉(zhuǎn)換取決于子問題的堆疊方式递胧，如果狀態(tài)定義得不合適，會導(dǎo)致子問題之間沒有重疊赡茸，也就不存在狀態(tài)轉(zhuǎn)換關(guān)系了缎脾。沒有狀態(tài)轉(zhuǎn)換關(guān)系，動態(tài)規(guī)劃也就沒有意義了占卧，實際算法就退化為像分治法那樣的樸素遞歸搜索算法了遗菠。

0-1 背包問題的決策很簡單，那就是決定是否選擇第 i 件物品华蜒，即判斷裝入第 i 件物品獲得的收益最大還是不裝入第 i 件物品獲得的收益最大舷蒲。如果不裝入第 i 件物品，則背包內(nèi)物品的價值仍然是 s[i-1,j] 狀態(tài)友多，如果裝入第 i 件物品牲平，則背包內(nèi)物品的價值就變成了 s[i,j-Vi] + Pi 狀態(tài)，其中 Vi 和 Pi 分別是第 i 件物品的容積和價值域滥，決策的狀態(tài)轉(zhuǎn)換方程就是：

                                  s[i,j]=max(s[i?1,j],s[i,j?Vi]+Pi)

最長公共子序列問題的決策方式就是判斷 str1[i] 和 str2[j] 的關(guān)系纵柿，如果 str1[i] 與 str2[j] 相同蜈抓，則公共子序列的長度應(yīng)該是 s[i-1,j-1] + 1， 否則就分別嘗試匹配 str1[1…i+1] 與 str2[1…j] 的最長公共子序列昂儒，以及 str1[1…i] 與 str2[1…j+1] 的最長公共子序列沟使，然后取二者中較大的那個值作為 s[i,j] 的值。最長公共子序列問題的狀態(tài)轉(zhuǎn)換方程就是：

                                          s[i,j]=s[i?1,j?1]+1

其中渊跋， str1[i] 與 str2[j] 相同腊嗡。

                                    s[i,j]=max(s[i,j?1],s[i?1,j])

其中， str1[i] 與 str2[j] 不相同拾酝。

確定邊界條件

對于遞歸加備忘錄方式（記憶搜索）實現(xiàn)的動態(tài)規(guī)劃方法燕少，邊界條件實際上就是遞歸終結(jié)條件，無需額外的計算蒿囤。對于使用遞推關(guān)系直接實現(xiàn)的動態(tài)規(guī)劃方法客们，需要確定狀態(tài)轉(zhuǎn)換方程的遞推式的初始條件或邊界條件，否則無法開始遞推計算材诽。

0-1 背包問題的邊界條件很簡單底挫，就是沒有裝入任何物品的狀態(tài)：

                                            s[0,Vmax]=0

若要確定最長公共子序列問題的邊界條件，要從其決策方式入手脸侥，當(dāng)兩個字符串中的一個長度為 0 時建邓，其公共子序列長度肯定是 0，因此其邊界條件就是：

                                      s[i,j]=0

其中睁枕，i=0 或 j=0官边。

最長公共子序列（LCS）問題

這一課我們用一個經(jīng)典的最長公共子序列問題為例，來說明一下如何將上面的原理分析應(yīng)用到算法實現(xiàn)過程中譬重。最長公共子序列（LCS，Longest Common Subsequence）的定義是：一個序列 S罐氨，如果分別是兩個或多個已知序列的子序列臀规，且是符合此條件的子序列中最長的，則稱 S 為已知序列的最長公共子序列栅隐。

關(guān)于子序列的定義通常有兩種方式塔嬉，一種是對子序列沒有連續(xù)的要求，其子序列的定義就是原序列中刪除若干元素后得到的序列租悄；另一種是對子序列有連續(xù)的要求谨究，其子序列的定義是原序列中連續(xù)出現(xiàn)的若干個元素組成的序列。

求解子序列是非連續(xù)的最長公共子序列問題泣棋，也是一個十分實用的問題胶哲，它可以描述兩段文字之間的“相似度”，即它們的雷同程度潭辈，從而能夠用來辨別抄襲鸯屿。下面將介紹對子序列沒有連續(xù)性要求的情況下應(yīng)如何用動態(tài)規(guī)劃法來解決最長公共子序列問題澈吨。

根據(jù)前面的分析，假如有兩個字符串 str1[1..m] 和 str2[1..n] 寄摆，其最長公共子序列問題在某一個決策階段的狀態(tài) s[i,j] 定義為 str1[1…i] 與 str2[1…j] 的最長公共子序列長度（i<=m, j<=n）谅辣，這個狀態(tài) s[i,j] 其實也就是子問題的定義，可以將其描述為：求字符串 str1<1..m> 中從第 1 個到第 i（i <= m） 個字符組成的子串 str1<1…i> 和字符串 str2<1..n> 中從第 1 個到第 j(j <= n) 個字符組成的子串 str2<1…j> 的最長公共序列婶恼。

接下來要找出子問題的最優(yōu)序列中狀態(tài) s[i,j] 的遞推關(guān)系桑阶。分析 s[i,j] 的遞推關(guān)系要從 str1[i] 和 str2[j] 的關(guān)系入手，根據(jù)非連續(xù)最長公共子序列問題的定義勾邦，如果 str1[i] 和 str2[j] 相同蚣录，則 s[i,j] 就是 s[i-1,j-1] 的最長公共序列 ＋1，如果 str1[i] 和 str2[j] 不相同检痰，則 s[i,j] 就是 s[i-1,j] 的最長公共序列和 s[i,j-1] 的最長公共序列中較大的那一個包归。

最后是確定狀態(tài)轉(zhuǎn)移遞推關(guān)系的邊界值。很顯然铅歼，當(dāng) str1 和 str2 中任何一個的長度為 0公壤，則其最長公共子序列即為 0，當(dāng)狀態(tài)遞推到 s[m,n] 時椎椰， s[m,n] 就是原始問題的最長公共子序列長度厦幅。完整的狀態(tài)轉(zhuǎn)移遞推關(guān)系如下：

DpLcs() 函數(shù)是用動態(tài)規(guī)劃法解決最長公共子序列問題的算法實現(xiàn)，從下面的代碼中可以看出慨飘，兩個 for 循環(huán)實際上是做了個廣域搜索确憨，將所有子序列的結(jié)果都求出來了，只有 s[m,n] 代表的是原始問題的最長公共子序列長度瓤的。

int DpLcs(const std::string& str1, const std::string& str2, int s[MAX_STRING_LEN][MAX_STRING_LEN])
{
    std::string::size_type i,j;

    for(i = 1; i <= str1.length(); i++)
        s[i][0] = 0;
    for(j = 1; j <= str2.length(); j++)
        s[0][j] = 0;

    for(i = 1; i <= str1.length(); i++)
    {
        for(j = 1; j <= str2.length(); j++)
        {
            if((str1[i - 1] == str2[j - 1]))
            {
                s[i][j] = s[i - 1][j - 1] + 1; 
            }
            else
            {
                s[i][j] = std::max(s[i - 1][j], s[i][j - 1]); 
            }
        }
    }

    return s[str1.length()][str2.length()];
}