????《Dynamic Programming》中的 “Programming”? 不是編程的意思，而是一種表格處理法。我們把每一步得到的子問題結(jié)果存儲在表格里，每次遇到該子問題時(shí)不需要再求解一遍，只需要查詢表格即可。

????動態(tài)規(guī)劃也是一種分治思想，但與分治算法不同的是，分治算法是把原問題分解為若干干子問題，自頂向下求解各個(gè)子問題，合并子問題的解，從而得到原問題的解。動態(tài)規(guī)劃也是把原問題分解為若干子問題，然后自底向上，先求解最小的子問題，把結(jié)果存儲在表格中，在求解大的子問題時(shí)，直接從表格中查詢小的子問題的解，避免重復(fù)計(jì)算，從而提高算法效率。

使用動態(tài)規(guī)劃求解的基本條件：

????（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é)果存儲在表中，以后使用時(shí)可以直接查詢，不需要再次求解。子問題重疊不是使用動態(tài)規(guī)劃的必要條件，但存在子問題重疊更能夠充分彰顯動態(tài)規(guī)劃的優(yōu)勢。

????? ? ??例如下面的斐波那契數(shù)列，大量子問題重疊

????（3）無后效性

????????動態(tài)規(guī)劃是將原問題分解為若干個(gè)重疊子問題，每個(gè)子問題的求解過程作為一個(gè)階段，完成前一個(gè)階段后，根據(jù)前一個(gè)階段的結(jié)果求解下一個(gè)階段。當(dāng)前階段的求解只和前面階段有關(guān)，和后續(xù)階段無關(guān)，稱為" 無后效性" 。

????????動態(tài)規(guī)劃的狀態(tài)空間構(gòu)成一個(gè)有向無環(huán)圖，圖中結(jié)點(diǎn)對應(yīng)問題的 “狀態(tài)”，圖中的邊對應(yīng)狀態(tài)之間的 “轉(zhuǎn)移”，選擇向哪個(gè)結(jié)點(diǎn)轉(zhuǎn)移就是 “決策”。遞歸式實(shí)際上就是 “狀態(tài)轉(zhuǎn)移方程” 。

????求解動態(tài)規(guī)劃問題，如何確定狀態(tài)和轉(zhuǎn)移方程是關(guān)鍵，也是難點(diǎn)。不同的狀態(tài)和轉(zhuǎn)移方程可能導(dǎo)致不同的算法復(fù)雜度。

????遇到一個(gè)實(shí)際問題，如何采用動態(tài)規(guī)劃來解決呢？

????????（1）分析最優(yōu)解的結(jié)構(gòu)特征。

????????（2）建立最優(yōu)值的遞歸式。

????????（3）自底向上計(jì)算最優(yōu)值，并記錄。

????????（4）構(gòu)造最優(yōu)解。

????

????