什么樣的問題適合用動態(tài)規(guī)劃來解決呢？換句話說，動態(tài)規(guī)劃能解決的問題有什么規(guī)律可循呢？實際上，動態(tài)規(guī)劃作為一個非常成熟的算法思想，很多人對此已經(jīng)做了非常全面的總結(jié)。我把這部分理論總結(jié)為“一個模型三個特征”。
一個模型
它指的是動態(tài)規(guī)劃適合解決的問題的模型。我把這個模型定義為“多階段決策最優(yōu)解模型”。
我們一般是用動態(tài)規(guī)劃來解決最優(yōu)問題。而解決問題的過程，需要經(jīng)歷多個決策階段。每個決策階段都對應著一組狀態(tài)。然后我們尋找一組決策序列，經(jīng)過這組決策序列，能夠產(chǎn)生最終期望求解的最優(yōu)值。
三個特征
- 最優(yōu)子結(jié)構(gòu)：最優(yōu)子結(jié)構(gòu)指的是，問題的最優(yōu)解包含子問題的最優(yōu)解。反過來說就是，我們可以通過子問題的最優(yōu)解，推導出問題的最優(yōu)解。如果我們把最優(yōu)子結(jié)構(gòu)，對應到我們前面定義的動態(tài)規(guī)劃問題模型上，那我們也可以理解為，后面階段的狀態(tài)可以通過前面階段的狀態(tài)推導出來。
- 無后效性：無后效性有兩層含義，第一層含義是，在推導后面階段的狀態(tài)的時候，我們只關(guān)心前面階段的狀態(tài)值，不關(guān)心這個狀態(tài)是怎么一步一步推導出來的。第二層含義是，某階段狀態(tài)一旦確定，就不受之后階段的決策影響。無后效性是一個非?！皩捤伞钡囊蟆Ｖ灰獫M足前面提到的動態(tài)規(guī)劃問題模型，其實基本上都會滿足無后效性。
- 重復子問題：這個概念比較好理解。如果用一句話概括一下，那就是，不同的決策序列，到達某個相同的階段時，可能會產(chǎn)生重復的狀態(tài)。
兩種動態(tài)規(guī)劃解題思路
1. 狀態(tài)轉(zhuǎn)移表法
一般能用動態(tài)規(guī)劃解決的問題，都可以使用回溯算法的暴力搜索解決。所以，當我們拿到問題的時候，我們可以先用簡單的回溯算法解決，然后定義狀態(tài)，每個狀態(tài)表示一個節(jié)點，然后對應畫出遞歸樹。從遞歸樹中，我們很容易可以看出來，是否存在重復子問題，以及重復子問題是如何產(chǎn)生的。以此來尋找規(guī)律，看是否能用動態(tài)規(guī)劃解決。
找到重復子問題之后，接下來，我們有兩種處理思路，第一種是直接用回溯加“備忘錄”的方法，來避免重復子問題。從執(zhí)行效率上來講，這跟動態(tài)規(guī)劃的解決思路沒有差別。第二種是使用動態(tài)規(guī)劃的解決方法，狀態(tài)轉(zhuǎn)移表，也是今天的重點。
狀態(tài)轉(zhuǎn)移表法是如何工作的？我們可以先畫出一個狀態(tài)表。狀態(tài)表一般都是二維的，所以你可以把它想象成二維數(shù)組。其中，每個狀態(tài)包含三個變量，行、列、數(shù)組值。我們根據(jù)決策的先后過程，從前往后，根據(jù)遞推關(guān)系，分階段填充狀態(tài)表中的每個狀態(tài)。最后，我們將這個遞推填表的過程，翻譯成代碼，就是動態(tài)規(guī)劃代碼了。
盡管大部分狀態(tài)表都是二維的，但是如果問題的狀態(tài)比較復雜，需要很多變量來表示，那對應的狀態(tài)表可能就是高維的，比如三維、四維。那這個時候，我們就不適合用狀態(tài)轉(zhuǎn)移表法來解決了。一方面是因為高維狀態(tài)轉(zhuǎn)移表不好畫圖表示，另一方面是因為人腦確實很不擅長思考高維的東西。
狀態(tài)轉(zhuǎn)移表法解題思路大致可以概括為，回溯算法實現(xiàn) - 定義狀態(tài) - 畫遞歸樹 - 找重復子問題 - 畫狀態(tài)轉(zhuǎn)移表 - 根據(jù)遞推關(guān)系填表 - 將填表過程翻譯成代碼。
2. 狀態(tài)轉(zhuǎn)移方程
狀態(tài)轉(zhuǎn)移方程法有點類似遞歸的解題思路。我們需要分析，某個問題如何通過子問題來遞歸求解，也就是所謂的最優(yōu)子結(jié)構(gòu)。根據(jù)最優(yōu)子結(jié)構(gòu)，寫出遞歸公式，也就是所謂的狀態(tài)轉(zhuǎn)移方程。有了狀態(tài)轉(zhuǎn)移方程，代碼實現(xiàn)就非常簡單了。一般情況下，我們有兩種代碼實現(xiàn)方法，一種是遞歸加“備忘錄”，另一種是迭代遞推。
min(i, j) = w[i][j] + min(min(i, j-1), min(i-1, j))
上面的方程就是狀態(tài)轉(zhuǎn)移方程，如果我們能寫出狀態(tài)轉(zhuǎn)移方程，那動態(tài)規(guī)劃問題基本上就解決一大半了，而翻譯成代碼非常簡單。但是很多動態(tài)規(guī)劃問題的狀態(tài)本身就不好定義，狀態(tài)轉(zhuǎn)移方程也就更不好想到。狀態(tài)轉(zhuǎn)移方程是解決動態(tài)規(guī)劃的關(guān)鍵。
狀態(tài)轉(zhuǎn)移方程法的大致思路可以概括為，找最優(yōu)子結(jié)構(gòu) - 寫狀態(tài)轉(zhuǎn)移方程 - 將狀態(tài)轉(zhuǎn)移方程翻譯成代碼。
最后
不是每個問題都同時適合這兩種解題思路。有的問題可能用第一種思路更清晰，而有的問題可能用第二種思路更清晰，所以，你要結(jié)合具體的題目來看，到底選擇用哪種解題思路。
