動態規劃的概念 在上例的多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最最佳化問題的方法為動態規劃方法。 動態規劃的最最佳化概念是在一定條件下，我到一種途徑，在對各階段的效益經過按問題具體性質所確定的運算以後，使得全過程的總效益達到最優。 應用動態規劃要注意階段的劃分是關鍵，必須依據題意分析，尋求合理的劃分階段(子問題)方法。而每個子問題是一個比原問題簡單得多的最佳化問題。而且每個子問題的求解中，均利用它的一個後部子問題的最最佳化結果，直到最後一個子問題所得最優解，它就是原問題的最優解。 1.3 動態規劃適合解決什麼樣的問題 準確地說，動態規劃不是萬能的，它只適於解決一定條件的最優策略問題。 或許，大家聽到這個結論會很失望:其實，這個結論並沒有削減動態規劃的光輝，因為屬於上面範圍內的問題極多，還有許多看似不是這個範圍中的問題都可以轉化成這類問題。 上面所說的“滿足一定條件”主要指下面兩點: (1)狀態必須滿足最最佳化原理; (2)狀態必須滿足無後效性。 動態規劃的最最佳化原理是無論過去的狀態和決策如何，對前面的決策所形成的當前狀態而言，餘下的諸決策必須構成最優策略。 可以通俗地理解為子問題的區域性最優將導致整個問題的全域性最優在上例中例題1最短路徑問題中，A到E的最優路徑上的任一點到終點E的路徑也必然是該點到終點E的一條最優路徑，滿足最最佳化原理。 動態規劃的無後效性原則某階段的狀態一旦確定，則此後過程的演變不再受此前各狀態及決策的影響。也就是說，“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之後，階段 I 中的狀態只能由階段 I+1 中的狀態透過狀態轉移方程得來，與其他狀態沒有關係，特別是與未發生的狀態沒有關係，這就是無後效性。