動態(tài)規(guī)劃：根據(jù)一類多階段問題的特點，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。即使是一些靜態(tài)模型，只要人為的引進“時間”因素，分成時段，就可以轉化為多階段的動態(tài)模型，用動態(tài)規(guī)劃去處理。
動態(tài)規(guī)劃求解的問題需要滿足一定的條件：
- 最優(yōu)化原理
- 無后效應
最優(yōu)化原理
最優(yōu)化原理：不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。簡單來說就是一個最優(yōu)策略的子策略也是必須是最優(yōu)的，所有子問題的局部最優(yōu)解將導致整個問題的全局最優(yōu)解。
最優(yōu)化原理是動態(tài)規(guī)劃的基礎，任何一個問題，如果失去最優(yōu)化原理的額支持，就不可能用動態(tài)規(guī)劃解決
舉個的例子說明：
如上圖，求從A點到E點的最短距離，假如最短距離的路線經過圖中的B點，那么子問題就是求從A點到B點之間的最短距離。
那么這個問題里，怎么證明最優(yōu)化原理呢？
我們假設從A點到E點的最短距離為d，其最優(yōu)策略的子策略假設經過B點，記該策略中B點到E點的距離為d1，A點到B點的距離為d2。我們可以使用反證法，假設存在B點到E點的最短距離d3，并且d3 < d1，那么 d3 + d2 < d1 + d2 = d，這與d是最短距離相矛盾，所以，d1是B點到E點的最短距離。
為了增加理解，這里再舉一個反例：
圖中有四個點，A、B、C、D，相鄰兩點有兩條連線，代表兩條通道，d1,d2,d3,d4,d5,d6代表的是道路的長度，求A到D的所有通道中，總長度除以4得到的余數(shù)最小的路徑為最優(yōu)路徑，求一條最優(yōu)路徑。
按照最優(yōu)化原理，A的最優(yōu)取值應該可以由B的最優(yōu)取值來確定，而B的最優(yōu)取值為（3+5）mod 4 = 0，所以應該選d2和d6這兩條道路。而實際上，全局最優(yōu)解是d4+d5+d6或者d1+d5+d3。所以這里子問題的最優(yōu)解并不是原問題的最優(yōu)解，即不滿足最優(yōu)化原理。所以就不適合使用動態(tài)規(guī)劃來求解了
無后效應
無后效應：下一時刻的狀態(tài)只與當前狀態(tài)有關，而與當前狀態(tài)之前的狀態(tài)無關，當前狀態(tài)是對以往策略的總結。換句話說，過去做的選擇不會影響現(xiàn)在能做的最優(yōu)選擇，現(xiàn)在能做的最優(yōu)選擇只與當前的狀態(tài)有關，與經過如何復雜的決策到達該狀態(tài)的方式無關。
在上面的最短路徑問題上，加上一個限制條件：同一個格子只能通過一次。
那么， 這個題就不符合無后效性了，因為前一個子問題的解會對后面子問題的選擇策略有影響，比如說，如果從A到B選擇了一條如下圖中綠色表示的路線，那么從B點出發(fā)到達E點的路線就只有一條了。也就是說從A點到B點的路徑選擇會影響B(tài)點到E點的路徑選擇
問題解決思路
動態(tài)規(guī)劃的理論設計都有一定的模式，一般需要經歷一下幾個步驟：
初始狀態(tài) -> |決策1| -> |決策2| -> |決策3|...-> |決策n| -> 結束狀態(tài)
- 劃分階段：按照問題的時間或空間特征，把問題分為若干階段
- 確定狀態(tài)或者狀態(tài)變量：將問題發(fā)展到各個階段所處于的各種客觀情況用不同的狀態(tài)標識出來
- 確定決策并寫出狀態(tài)轉移方程：如果確定了決策，狀態(tài)轉移方程也可寫出，但事實上常常是反過來做，根據(jù)相鄰兩段個狀態(tài)之間的關系來確定決策。
- 尋找邊界條件：給出的狀態(tài)轉移方程是一個遞歸式，需要一個遞推的終止條件或邊界條件
使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃三要素：
- 問題的階段
- 每個階段的狀態(tài)
- 從前一個階段轉化為后一個階段之間的遞推關系
其中遞推關系必須是從次小的問題開始到較大的問題之間的轉化。
從這個角度來講，動態(tài)規(guī)劃往往可以用遞歸程序實現(xiàn)，不給過遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢。
設計算法實現(xiàn)步驟：
- 問題抽象化
- 建模
- 尋找約束條件
- 尋找遞推關系式
- 確定初始值
