本文來自通俗易懂算法入門書《趣學(xué)算法》。
動態(tài)規(guī)劃是1957年理查德·貝爾曼在《Dynamic Programming》一書中提出來的，八卦一下，這個人可能有同學(xué)不知道，但他的一個算法你可能聽說過，他和萊斯特·福特一起提出了求解最短路徑的Bellman-Ford 算法，該算法解決了Dijkstra算法不能處理負權(quán)值邊的問題。
Dynamic Programming，這里的Programming不是編程的意思，而是指一種表格處理法。我們把每一步得到的子問題結(jié)果存儲在表格里，每次遇到該子問題時不需要再求解一遍，只需要查詢表格即可。
4.1.1 算法思想
動態(tài)規(guī)劃也是一種分治思想，但與分治算法不同的是，分治算法是把原問題分解為若干子問題，自頂向下，求解各子問題，合并子問題的解從而得到原問題的解。動態(tài)規(guī)劃也是把原問題分解為若干子問題，然后自底向上，先求解最小的子問題，把結(jié)果存儲在表格中，在求解大的子問題時，直接從表格中查詢小的子問題的解，避免重復(fù)計算，從而提高算法效率。
4.1.2 算法要素
什么問題可以使用動態(tài)規(guī)劃呢？我們首先要分析問題是否具有以下兩個性質(zhì)：
（1）最優(yōu)子結(jié)構(gòu)
最優(yōu)子結(jié)構(gòu)性質(zhì)是指問題的最優(yōu)解包含其子問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是使用動態(tài)規(guī)劃的最基本條件，如果不具有最優(yōu)子結(jié)構(gòu)性質(zhì)就不可以使用動態(tài)規(guī)劃解決。
（2）子問題重疊
子問題重疊是指在求解子問題的過程中，有大量的子問題是重復(fù)的，那么只需要求解一次，然后把結(jié)果存儲在表中，以后使用時可以直接查詢，不需要再次求解。子問題重疊不是使用動態(tài)規(guī)劃的必要條件，但問題存在子問題重疊更能夠充分彰顯動態(tài)規(guī)劃的優(yōu)勢。
什么問題可以使用動態(tài)規(guī)劃呢？我們首先要分析問題是否具有以下兩個性質(zhì)：
（1）最優(yōu)子結(jié)構(gòu)
最優(yōu)子結(jié)構(gòu)性質(zhì)是指問題的最優(yōu)解包含其子問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是使用動態(tài)規(guī)劃的最基本條件，如果不具有最優(yōu)子結(jié)構(gòu)性質(zhì)就不可以使用動態(tài)規(guī)劃解決。
（2）子問題重疊
子問題重疊是指在求解子問題的過程中，有大量的子問題是重復(fù)的，那么只需要求解一次，然后把結(jié)果存儲在表中，以后使用時可以直接查詢，不需要再次求解。子問題重疊不是使用動態(tài)規(guī)劃的必要條件，但問題存在子問題重疊更能夠充分彰顯動態(tài)規(guī)劃的優(yōu)勢。
4.1.1 解題秘籍
遇到一個實際問題，如何采用動態(tài)規(guī)劃來解決呢？
（1） 分析最優(yōu)解的結(jié)構(gòu)特征。
（2） 建立最優(yōu)值的遞歸式。
（3） 自底向上計算最優(yōu)值，并記錄。
（4） 構(gòu)造最優(yōu)解。
本章通過8個實例，講解了動態(tài)規(guī)劃的解題過程。動態(tài)規(guī)劃求解最優(yōu)化問題時需要考慮兩個性質(zhì)：最優(yōu)子結(jié)構(gòu)和子問題重疊，只要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)就可以使用動態(tài)規(guī)劃，如果還具有子問題重疊，則更能彰顯動態(tài)規(guī)劃的優(yōu)勢。判斷可以使用動態(tài)規(guī)劃后，就可以分析其最優(yōu)子結(jié)構(gòu)特征，找到原問題和子問題的關(guān)系，從而得到最優(yōu)解遞歸式。然后按照最優(yōu)解遞歸式自底向上求解，采用備忘機制(查表法)有效解決子問題重疊，重復(fù)的子問題不需要重復(fù)求解，只需查表即可。
動態(tài)規(guī)劃的關(guān)鍵：
(1)最優(yōu)子結(jié)構(gòu)判定
a. 作出一個選擇；
b. 假定已經(jīng)知道了哪種選擇是最優(yōu)的；
例如矩陣連乘問題，我們假設(shè)已經(jīng)知道在第k個矩陣加括號是最優(yōu)的，即(AiAi+1…Ak)(Ak+1Ak+2…Aj)。
c. 最優(yōu)選擇后會產(chǎn)生哪些子問題；
例如矩陣連乘問題，我們作出最優(yōu)選擇后產(chǎn)生兩個子問題：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)。
d. 證明原問題的最優(yōu)解包含其子問題的最優(yōu)解。
通常使用“剪切—粘貼”反證法。證明如果原問題的解是最優(yōu)解，那么子問題的解也是最優(yōu)解。反證：假定子問題的解不是最優(yōu)解，那么就可以將它“剪切”掉，把最優(yōu)解“粘貼”進去，從而得到一個比原問題最優(yōu)解更優(yōu)的解，這與前提原問題的解是最優(yōu)解矛盾。得證。
例如：矩陣連乘問題，c=a+b+d，我們只需要證明如果c是最優(yōu)的，則a和b一定是最優(yōu)的（即原問題的最優(yōu)解包含子問題的最優(yōu)解）。
反證法：如果a不是最優(yōu)的，(AiAi+1…Ak) 存在一個最優(yōu)解aˊ，aˊ
(2)如何得到最優(yōu)解遞歸式
a.分析原問題最優(yōu)解和子問題最優(yōu)解的關(guān)系；
例如矩陣連乘問題，我們假設(shè)已經(jīng)知道在第k個矩陣加括號是最優(yōu)的，即(AiAi+1…Ak)(Ak+1Ak+2…Aj)。作出最優(yōu)選擇后產(chǎn)生兩個子問題：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)。如果我們用m[i][j]表示AiAi+1…Aj矩陣連乘的最優(yōu)解，那么兩個子問題：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)對應(yīng)的最優(yōu)解分別是m[i][k]，m[k+1][j]。剩下的只需要考察(AiAi+1…Ak)和(Ak+1Ak+2…Aj)的結(jié)果矩陣相乘的乘法次數(shù)了。兩個結(jié)果矩陣相乘的乘法次數(shù)是pi*pk+1*qj。
因此，原問題最優(yōu)解和子問題最優(yōu)解的關(guān)系：m[i][j]= m[i][k]+m[k+1][j]+ pi*pk+1*qj
b.考察有多少種選擇；
實質(zhì)上，我們并不知道哪種選擇是最優(yōu)的，因此就需要考察有多少種選擇，然后從這些選擇中找到最優(yōu)解。
例如矩陣連乘問題，加括號的位置k(AiAi+1…Ak)(Ak+1Ak+2…Aj)，k的取值范圍是{i，i+1，…，j-1}，即i≤k
c.得到最優(yōu)解遞歸式。
例如矩陣連乘問題，m[i][j]表示AiAi+1…Aj矩陣連乘的最優(yōu)解，根據(jù)最優(yōu)解和子問題最優(yōu)解的關(guān)系，并考察所有的選擇，找到最小值就是我們要的最優(yōu)解。
