什麼是動態規劃？動態規劃的意義是什麼？

11-25

動態規劃中遞推式的求解方法不是動態規劃的本質。

我曾經作為省隊成員參加過NOI，保送之後也給學校參加NOIP的同學多次講過動態規劃，我試著講一下我理解的動態規劃，爭取深入淺出。希望你看了我的答案，能夠喜歡上動態規劃。

0. 動態規劃的本質，是對問題狀態的定義和狀態轉移方程的定義。
引自維基百科

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

動態規劃是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。
本題下的其他答案，大多都是在說遞推的求解方法，但如何拆分問題，才是動態規劃的核心。
而拆分問題，靠的就是狀態的定義和狀態轉移方程的定義。

1. 什麼是狀態的定義？

首先想說大家千萬不要被下面的數學式嚇到，這裡只涉及到了函數相關的知識。
我們先來看一個動態規劃的教學必備題：

給定一個數列，長度為N，
求這個數列的最長上升（遞增）子數列（LIS）的長度.
以
1 7 2 8 3 4
為例。
這個數列的最長遞增子數列是 1 2 3 4，長度為4；
次長的長度為3，包括 1 7 8; 1 2 3 等.

要解決這個問題，我們首先要定義這個問題和這個問題的子問題。
有人可能會問了，題目都已經在這了，我們還需定義這個問題嗎？需要，原因就是這個問題在字面上看，找不出子問題，而沒有子問題，這個題目就沒辦法解決。

所以我們來重新定義這個問題：

給定一個數列，長度為N，
設 $F_{k}$ 為：以數列中第k項結尾的最長遞增子序列的長度.
求 $F_{1}..F_{N}$ 中的最大值.

顯然，這個新問題與原問題等價。
而對於 $F_{k}$ 來講， $F_{1} .. F_{k-1}$ 都是 $F_{k}$ 的子問題：因為以第k項結尾的最長遞增子序列（下稱LIS），包含著以第 $1..k-1$ 中某項結尾的LIS。

上述的新問題 $F_{k}$ 也可以叫做狀態，定義中的「 $F_{k}$ 為數列中第k項結尾的LIS的長度」，就叫做對狀態的定義。
之所以把 $F_{k}$ 做「狀態」而不是「問題」，一是因為避免跟原問題中「問題」混淆，二是因為這個新問題是數學化定義的。

對狀態的定義只有一種嗎？當然不是。
我們甚至可以二維的，以完全不同的視角定義這個問題：

給定一個數列，長度為N，
設 $F_{i, k}$ 為：
在前i項中的，長度為k的最長遞增子序列中，最後一位的最小值. $1leq kleq N$ .
若在前i項中，不存在長度為k的最長遞增子序列，則 $F_{i, k}$ 為正無窮.
求最大的x，使得 $F_{N,x}$ 不為正無窮。

這個新定義與原問題的等價性也不難證明，請讀者體會一下。
上述的 $F_{i, k}$ 就是狀態，定義中的「 $F_{i, k}$ 為：在前i項中，長度為k的最長遞增子序列中，最後一位的最小值」就是對狀態的定義。

2. 什麼是狀態轉移方程？
上述狀態定義好之後，狀態和狀態之間的關係式，就叫做狀態轉移方程。

比如，對於LIS問題，我們的第一種定義：

設 $F_{k}$ 為：以數列中第k項結尾的最長遞增子序列的長度.

設A為題中數列，狀態轉移方程為：

$F_{1} = 1$ （根據狀態定義導出邊界情況）
$F_{k}=max(F_{i}+1 | A_{k}>A_{i}, iin (1..k-1))$ $(k>1)$

用文字解釋一下是：
以第k項結尾的LIS的長度是：保證第i項比第k項小的情況下，以第i項結尾的LIS長度加一的最大值，取遍i的所有值（i小於k）。

第二種定義：

設 $F_{i, k}$ 為：在數列前i項中，長度為k的遞增子序列中，最後一位的最小值

設A為題中數列，狀態轉移方程為：

若 $A_{i}>F_{i-1,k-1}$ 則 $F_{i,k}=min(A_{i},F_{i-1,k})$
否則： $F_{i,k}=F_{i-1,k}$

（邊界情況需要分類討論較多，在此不列出，需要根據狀態定義導出邊界情況。）
大家套著定義讀一下公式就可以了，應該不難理解，就是有點繞。

這裡可以看出，這裡的狀態轉移方程，就是定義了問題和子問題之間的關係。
可以看出，狀態轉移方程就是帶有條件的遞推式。

3. 動態規劃迷思
本題下其他用戶的回答跟動態規劃都有或多或少的聯繫，我也講一下與本答案的聯繫。

a. 「緩存」，「重疊子問題」，「記憶化」：
這三個名詞，都是在闡述遞推式求解的技巧。以Fibonacci數列為例，計算第100項的時候，需要計算第99項和98項；在計算第101項的時候，需要第100項和第99項，這時候你還需要重新計算第99項嗎？不需要，你只需要在第一次計算的時候把它記下來就可以了。
上述的需要再次計算的「第99項」，就叫「重疊子問題」。如果沒有計算過，就按照遞推式計算，如果計算過，直接使用，就像「緩存」一樣，這種方法，叫做「記憶化」，這是遞推式求解的技巧。這種技巧，通俗的說叫「花費空間來節省時間」。都不是動態規劃的本質，不是動態規劃的核心。

b. 「遞歸」：
遞歸是遞推式求解的方法，連技巧都算不上。

c. "無後效性"，「最優子結構」：
上述的狀態轉移方程中，等式右邊不會用到下標大於左邊i或者k的值，這是"無後效性"的通俗上的數學定義，符合這種定義的狀態定義，我們可以說它具有「最優子結構」的性質，在動態規劃中我們要做的，就是找到這種「最優子結構」。
在對狀態和狀態轉移方程的定義過程中，滿足「最優子結構」是一個隱含的條件（否則根本定義不出來）。對狀態和「最優子結構」的關係的進一步解釋，什麼是動態規劃？動態規劃的意義是什麼？ - 王勐的回答寫的很好，大家可以去讀一下。

需要注意的是，一個問題可能有多種不同的狀態定義和狀態轉移方程定義，存在一個有後效性的定義，不代表該問題不適用動態規劃。這也是其他幾個答案中出現的邏輯誤區：
動態規劃方法要尋找符合「最優子結構「的狀態和狀態轉移方程的定義，在找到之後，這個問題就可以以「記憶化地求解遞推式」的方法來解決。而尋找到的定義，才是動態規劃的本質。

有位答主說：

分治在求解每個子問題的時候，都要進行一遍計算
動態規劃則存儲了子問題的結果，查表時間為常數

這就像說多加辣椒的菜就叫川菜，多加醬油的菜就叫魯菜一樣，是存在誤解的。

文藝的說，動態規劃是尋找一種對問題的觀察角度，讓問題能夠以遞推（或者說分治）的方式去解決。尋找看問題的角度，才是動態規劃中最耀眼的寶石！（大霧）

動態規劃的本質不在於是遞推或是遞歸，也不需要糾結是不是內存換時間。

理解動態規劃並不需要數學公式介入，只是完全解釋清楚需要點篇幅…首先需要明白哪些問題不是動態規劃可以解決的，才能明白為神馬需要動態規劃。不過好處時順便也就搞明白了遞推貪心搜索和動規之間有什麼關係，以及幫助那些總是把動規當成搜索解的同學建立動規的思路。當然熟悉了之後可以直接根據問題的描述得到思路，如果有需要的話再補充吧。

動態規劃是對於某一類問題的解決方法！！重點在於如何鑒定「某一類問題」是動態規劃可解的而不是糾結解決方法是遞歸還是遞推！

怎麼鑒定dp可解的一類問題需要從計算機是怎麼工作的說起…計算機的本質是一個狀態機，內存里存儲的所有數據構成了當前的狀態，CPU只能利用當前的狀態計算出下一個狀態（不要糾結硬碟之類的外部存儲，就算考慮他們也只是擴大了狀態的存儲容量而已，並不能改變下一個狀態只能從當前狀態計算出來這一條鐵律）

當你企圖使用計算機解決一個問題是，其實就是在思考如何將這個問題表達成狀態（用哪些變數存儲哪些數據）以及如何在狀態中轉移（怎樣根據一些變數計算出另一些變數）。所以所謂的空間複雜度就是為了支持你的計算所必需存儲的狀態最多有多少，所謂時間複雜度就是從初始狀態到達最終狀態中間需要多少步！

太抽象了還是舉個例子吧：

比如說我想計算第100個非波那契數，每一個非波那契數就是這個問題的一個狀態，每求一個新數字只需要之前的兩個狀態。所以同一個時刻，最多只需要保存兩個狀態，空間複雜度就是常數；每計算一個新狀態所需要的時間也是常數且狀態是線性遞增的，所以時間複雜度也是線性的。

上面這種狀態計算很直接，只需要依照固定的模式從舊狀態計算出新狀態就行（a[i]=a[i-1]+a[i-2]），不需要考慮是不是需要更多的狀態，也不需要選擇哪些舊狀態來計算新狀態。對於這樣的解法，我們叫遞推。

非波那契那個例子過於簡單，以至於讓人忽視了階段的概念，所謂階段是指隨著問題的解決，在同一個時刻可能會得到的不同狀態的集合。非波那契數列中，每一步會計算得到一個新數字，所以每個階段只有一個狀態。想像另外一個問題情景，假如把你放在一個圍棋棋盤上的某一點，你每一步只能走一格，因為你可以東南西北隨便走，所以你當你同樣走四步可能會處於很多個不同的位置。從頭開始走了幾步就是第幾個階段，走了n步可能處於的位置稱為一個狀態，走了這n步所有可能到達的位置的集合就是這個階段下所有可能的狀態。

現在問題來了，有了階段之後，計算新狀態可能會遇到各種奇葩的情況，針對不同的情況，就需要不同的演算法，下面就分情況來說明一下：

假如問題有n個階段，每個階段都有多個狀態，不同階段的狀態數不必相同，一個階段的一個狀態可以得到下個階段的所有狀態中的幾個。那我們要計算出最終階段的狀態數自然要經歷之前每個階段的某些狀態。

好消息是，有時候我們並不需要真的計算所有狀態，比如這樣一個弱智的棋盤問題：從棋盤的左上角到達右下角最短需要幾步。答案很顯然，用這樣一個弱智的問題是為了幫助我們理解階段和狀態。某個階段確實可以有多個狀態，正如這個問題中走n步可以走到很多位置一樣。但是同樣n步中，有哪些位置可以讓我們在第n+1步中走的最遠呢？沒錯，正是第n步中走的最遠的位置。換成一句熟悉話叫做「下一步最優是從當前最優得到的」。所以為了計算最終的最優值，只需要存儲每一步的最優值即可，解決符合這種性質的問題的演算法就叫貪心。如果只看最優狀態之間的計算過程是不是和非波那契數列的計算很像？所以計算的方法是遞推。

既然問題都是可以劃分成階段和狀態的。這樣一來我們一下子解決了一大類問題：一個階段的最優可以由前一個階段的最優得到。

如果一個階段的最優無法用前一個階段的最優得到呢？

什麼你說只需要之前兩個階段就可以得到當前最優？那跟只用之前一個階段並沒有本質區別。最麻煩的情況在於你需要之前所有的情況才行。

再來一個迷宮的例子。在計算從起點到終點的最短路線時，你不能只保存當前階段的狀態，因為題目要求你最短，所以你必須知道之前走過的所有位置。因為即便你當前再的位置不變，之前的路線不同會影響你的之後走的路線。這時你需要保存的是之前每個階段所經歷的那個狀態，根據這些信息才能計算出下一個狀態！

每個階段的狀態或許不多，但是每個狀態都可以轉移到下一階段的多個狀態，所以解的複雜度就是指數的，因此時間複雜度也是指數的。哦哦，剛剛提到的之前的路線會影響到下一步的選擇，這個令人不開心的情況就叫做有後效性。

剛剛的情況實在太普遍，解決方法實在太暴力，有沒有哪些情況可以避免如此的暴力呢？

契機就在於後效性。

有一類問題，看似需要之前所有的狀態，其實不用。不妨也是拿最長上升子序列的例子來說明為什麼他不必需要暴力搜索，進而引出動態規劃的思路。

假裝我們年幼無知想用搜索去尋找最長上升子序列。怎麼搜索呢？需要從頭到尾依次枚舉是否選擇當前的數字，每選定一個數字就要去看看是不是滿足「上升」的性質，這裡第i個階段就是去思考是否要選擇第i個數，第i個階段有兩個狀態，分別是選和不選。哈哈，依稀出現了剛剛迷宮找路的影子！咦慢著，每次當我決定要選擇當前數字的時候，只需要和之前選定的一個數字比較就行了！這是和之前迷宮問題的本質不同！這就可以縱容我們不需要記錄之前所有的狀態啊！既然我們的選擇已經不受之前狀態的組合的影響了，那時間複雜度自然也不是指數的了啊！雖然我們不在乎某序列之前都是什麼元素，但我們還是需要這個序列的長度的。所以我們只需要記錄以某個元素結尾的LIS長度就好！因此第i個階段的最優解只是由前i-1個階段的最優解得到的，然後就得到了DP方程（感謝 @韓曦指正）
$LIS(i)=max{LIS(j)+1} j<i and a[j] < a[i]$

所以一個問題是該用遞推、貪心、搜索還是動態規劃，完全是由這個問題本身階段間狀態的轉移方式決定的！

每個階段只有一個狀態-&>遞推；
每個階段的最優狀態都是由上一個階段的最優狀態得到的-&>貪心；
每個階段的最優狀態是由之前所有階段的狀態的組合得到的-&>搜索；
每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到而不管之前這個狀態是如何得到的-&>動態規劃。

每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到

這個性質叫做最優子結構；

而不管之前這個狀態是如何得到的

這個性質叫做無後效性。

另：其實動態規劃中的最優狀態的說法容易產生誤導，以為只需要計算最優狀態就好，LIS問題確實如此，轉移時只用到了每個階段「選」的狀態。但實際上有的問題往往需要對每個階段的所有狀態都算出一個最優值，然後根據這些最優值再來找最優狀態。比如背包問題就需要對前i個包（階段）容量為j時（狀態）計算出最大價值。然後在最後一個階段中的所有狀態種找到最優值。

首先明確：動態規劃是用來求解最優化問題的一種方法。常規演算法書上強調的是無後效性和最優子結構描述，這套理論是正確的，但是適用與否與你的狀態表述有關。至於劃分階段什麼的就有些扯淡了：動態規劃不一定有所謂的階段。其實質是狀態空間的狀態轉移。

下面的理解為我個人十年競賽之總結。基本上在oi和acm中我沒有因為動態規劃而失手過。

所有的決策類求最優解的問題都是在狀態空間內找一個可以到達的最佳狀態。搜索的方式是去遍歷每一個點，而動態規劃則是把狀態空間變形，由此變成從初始到目標狀態的最短路問題。

依照這種描述：假若你的問題的結論包含若干決策，則可以認為從初始狀態（邊界條件）到解中間的決策流程是一個決策狀態空間中的轉移路線。前提是：你的狀態描述可以完整且唯一地覆蓋所有有效的狀態空間中的點，且轉移路線包含所有可能的路徑。

這個描述是包含動態規劃兩大條件的。所謂無後效性，指狀態間的轉移與如何到達某狀態無關。如果有關，意味著你的狀態描述不能完整而唯一地包括每一個狀態。如果你發現一個狀態轉移有後效性，很簡單，把會引起後效性的參數作為狀態描述的一部分放進去將其區分開來就可以了；最優子結構說明轉移路線包含了所有可能的路徑，如果不具備最優子結構，意味著有部分情況沒有在轉移中充分體現，增加轉移的描述就可以了。最終所有的搜索問題都可以描述成狀態空間內的狀態轉移方程，只是有可能狀態數量是指數階的，有可能不滿足計算要求罷了。

這樣的描述下，所有的動態規劃問題都可以轉變為狀態空間內大量可行狀態點和有效轉移構成的圖的從初始狀態到最終狀態的最短路問題。

於是乎，對於動態規劃，他的本質就是圖論中的最短路；階段可以去除，因為不一定有明確的階段劃分。

首先，我要回答你的第一個問題：什麼是動態規劃？

動態規劃是一種通過「大而化小」的思路解決問題的演算法。區別於一些固定形式的演算法，如二分法，寬度優先搜索法，動態規劃沒有實際的步驟來規定第一步做什麼第二步做什麼。所以更加確切的說，動態規劃是一種解決問題的思想。這種思想的本質是，一個規模比較大的問題（假如用2-3個參數可以表示），是通過規模比較小的若干問題的結果來得到的（通過取最大，取最小，或者加起來之類的運算）所以我們經常看到的動態規劃的核心——狀態轉移方程都長成這樣：

* f[i][j] = f[i - 1][j] + f[i][j - 1]

* f[i] = max{f[j] if j &< i and …} + 1

* f[i][j] = f[0][j - 1] judge(1,i) || f[1][j - 1] judge(2,i) || …

現在我要回答你的第二個問題了：動態規劃的意義是什麼？

動態規劃一般來說是「高效」的代名詞，因為其解決的問題一般退而求其次的演算法只有搜索了。以「數字三角形」一題為例子（http://www.lintcode.com/problem/triangle/ ），在「三角矩陣」中找一條從上到下的路徑，使得權值之和最小。如果使用暴力搜索的演算法，那麼需求窮舉出2^(n-1)條路徑（n為三角形高度），而使用動態規劃的話，則時間複雜度降低到了n^2，完成了質的飛躍。那麼究竟為什麼這麼快呢？原因在於動態規劃演算法去掉了「無用和重複的運算」。在搜索演算法中，假如從A-&>B有2條路徑，一條代價為10，另外一條代價為100，B-&>終點有1024條路徑。當我們選擇了代價為10的那條路徑走到B時，可以繼續往下走完1024條路徑到終點，但是在此之後，我們再從代價為100的路徑從A走到B時，我們可以發現此時無論如何走，都不可能有剛才從10的路徑走過來更好，所以這些計算是「無用」的計算，也可以說是「重複」的計算。這就是動態規劃之所以「快」的重要原因。

一般求最大值/最小值、求可不可行、求方案總數90%的概率是使用動態規劃來求解。要重點說明的是，如果一個問題讓你求出「所有的」方案和結果，則肯定不是使用動態規劃。

解決一個動態規劃問題首先根據「問5」判斷是否是動態規劃的問題，如果是，則嘗試將其按照「問4」進行分類，找到對應的類別和相似的問題。接著從下面的4個要素去逐步剖析解決這道題：

1. 狀態是什麼
2. 狀態轉移方程是什麼
3. 狀態的初始值是什麼
4. 問題要求的最後答案是什麼

每個步驟分析完成之後，就基本上解決了整道動態規劃的問題。

現在動態規劃在面試中考得很多，並且越來越多了。隨著CS從業與求職者的增加，並伴隨大家都是「有備而來」的情況下，一般簡單的反轉鏈表之類的題目已經無法再在面試中堅挺了。因此在求職者人數與招聘名額的比例較大的情況下，公司會傾向於出更難的面試問題。而動態規劃就是一種比較具有難度，又比較「好出」的面試問題。相比其他的演算法與數據結構知識來說，貪心法分治法太難出題了，搜索演算法往往需要耗費求職者過長的程序編寫時間一般也不傾向於出，二叉樹鏈表等問題題目並沒有那麼多，而且求職者也都會著重準備這一塊。因此動態規劃這一類的問題，便越來越多的出現在了面試中。

動態規劃的常見類型分為如下幾種：

* 矩陣型
* 序列型
* 雙序列型
* 劃分型
* 區間型
* 背包型
* 狀態壓縮型
* 樹型

其中，在技術面試中經常出現的是矩陣型，序列型和雙序列型。劃分型，區間型和背包型偶爾出現。狀態壓縮和樹型基本不會出現（一般在演算法競賽中才會出現）。

每種類型都有著自己的題目特點和狀態的表示方法。以矩陣型動態規劃為例，一般題目會給你一個矩陣，告訴你有一個小人在上面走動，每次只能向右和向下走，然後問你比如有多少種方案從左上走到右下 (http://www.lintcode.com/problem/unique-paths/)。這種類型狀態表示的特點一般是使用坐標作為狀態，如f[i][j]表示走到(i,j)這個位置的時候，一共有多少種方案。狀態的轉移則是考慮是從哪兒走到(i,j)這個坐標的。而序列型的動態規劃，一般是告訴你一個序列；雙序列的動態規劃一般是告訴你兩個字元串或者兩個序列。

將所做過的動態規劃問題按照這些類別進行歸類，分析狀態的表示方法和狀態轉移方程的構造方法在每種類型中的近似之處，會讓你更快的學會動態規劃。

希望對你有幫助~

搞過ACM的水貨答一下。
排名第一的答案本身已足夠好了，但還是太過專業，不能傳教於大眾，故試著來個通俗的答案。
首先，動態規劃是一種演算法。那麼，何謂演算法？計算機書籍中不難找到其嚴謹的學術定義，大眾可以簡單理解為「解決某一類問題的核心思想」。

先談動態規劃的意義——望文生義，「動態」規劃對應「動態」的問題：你並不知道問題的規模會有多大，而不論是個位數還是百萬級，都能以較快速度(動態規劃是一種泛用性演算法，而泛用性演算法與特定演算法相比往往存在性能差距)將結果正確計算出來。這是對於計算機科學最直觀的意義，當然我認為其對人生亦有一定指導意義，但那是見仁見智的事了。

動態規劃這一思想的實質其實是以下兩點：
1.分析問題，構造狀態轉移方程
2.以空間換時間

讓我們結合一個簡單例子來理解一下：
以乘法計算為例，乘法的定義其實是做n次加法，請先忘掉九九乘法表，讓你計算9*9，如何得到81這個解？計算9*10呢？9*999……以及9*n呢？
1.分析問題，構造狀態轉移方程
「狀態轉移方程」的學術定義亦可簡單找到（比如置頂答案），略去不表。光看「方程」二字，可以明白它是一個式子。
針對以上問題，我們構造它的狀態轉移方程。
問題規模小的時候，我們可以容易得到以下式子：
9*0=0；
9*1=0+9；
9*2=0+9+9；
……
可以得到：9*n=0+9+...+9(總共加了n個9)。嚴謹的證明可以使用數學歸納法，略去不表。
現在，定義dp(n)=9*n,改寫以上式子：
dp(0)=9*0=0；
dp(1)=9*1=dp(0)+9；
dp(2)=9*2=dp(1)+9；
……
作差易得：dp(n)=dp(n-1)+9；這就是狀態轉移方程了。
可以看到，有了狀態轉移方程，我們現在可以順利求解9*n（n為任意正整數）這一問題。
2.以空間換時間
雖然能解，但當n很大時，計算耗時過大，看不出狀態轉移方程dp(n)=dp(n-1)+9與普通方程9*n=0+9+...+9(總共加了n個9)相比沒有任何優勢。
這時，如果dp(n-1)的結果已知，dp(n)=dp(n-1)+9隻需計算一次加法，而9*n=0+9+...+9(總共加了n個9)則需計算n-1次加法，效率差異一望即知。
存儲計算結果，可令狀態轉移方程加速，而對普通方程沒有意義。
以空間換時間，是令動態規划具有實用價值的必備舉措。

@熊大大的回答真好，理解的準確又深刻。
我來試試看看能能不能能多創造一點價值：）

1. 動態規劃是解決問題的一種方法。
是的，它只是問題的一種解決方法。一個問題完全可能有多種解法。

2. 動態規劃的本質是它試圖將問題定義成這樣的形式：
「原問題的解如何由子問題的解組合而成。」

比如求解斐波那契數列的第n個數f(n)，用動態規劃解決這個問題就是要找出f(n)實際上是等於f(n-1) 加上 f(n-2)得到的。
當然這是最簡單的例子，很多問題在描述的時候並不能很顯然的看出原問題是否有子問題，原問題的解如何由子問題的解組合而成，這時試圖用動態規劃求解就需要變化看待原問題的角度，來獲得動態規劃的問題形式。

如果怎麼都無法將問題定義成這樣的形式，那麼很抱歉說明這個問題無法用動態規劃求解。
我們常常說的狀態轉移方程，其實就是「原問題的解如何由子問題的解組合而成」這句話的數學表達。
所以 @熊大大說「動態規劃的本質，是對問題狀態的定義和狀態轉移方程的定義。」，準確！（不過沒學過的同學可能緊接著要問這裡的狀態指什麼）

3. 對於有經驗的人來說，摸索出原問題的解如何由子問題組合而成，就能把狀態轉移方程寫出來，該問題就已經解決了。
因為動態規劃的實現有很成熟的兩類方法：
（1）「自頂向下」（top-down dynamic programming:）的實現方式
（2）「自低向上」（bottom-up dynamic programming：）的實現方式
有經驗的人由狀態轉移方程隨便選一種實現方式，就跟大部分高中試題一樣遵從套路即可。
所以，解動態規劃問題本質還是找出「原問題的解如何由子問題組合而成」，這是動態規劃的本質。

4. 到這裡就可以說明一下動態規劃與遞歸、caching的關係，
（1）遞歸只是動態規劃的一種實現方式，屬於「自頂向下」的實現方式。一個動態規劃問題在實現的時候完全是可以用非遞歸的方式來編碼實現的。
所以，遞歸不是動態規劃的本質。
（2）Caching是動態規劃實現過程中提升計算效率的一種方法，它的想法就是把計算過的值存起來，下次同樣的計算過程直接使用保存的結果即可。
Caching既可以用於遞歸實現，也可以用在非遞歸實現。
所以，Caching也不是動態規劃的本質。

4. 「自頂向下」的實現方式和「自低向上」的實現方式各有什麼優缺點，我的理解如下。
兩種方法的取捨我個人的喜好是——優先選擇Top-Down dynamic programming，除非不容易得到遞歸公式或空間複雜度無法接受。

「自頂向下」（top-down dynamic programming）：
1.能方便的得到遞歸公式，並用遞歸函數實現
2.保持了遞歸實現的代碼結構，邏輯上容易理解。
3.過程中只計算需要計算的子結果。
4.當採用了caching技術時多次被調用時天然的復用之前被調用時的子結果。（比如連續兩次計算fibonacci數F(4), F(5),則計算F(5)時已知F(3)和F(4)，直接相加即可）

「自低向上」（bottom-up dynamic programming）：
1.需要設計數據結構來完成自底向上的計算過程。邏輯上相對不那麼直觀。
2.常常可以進行空間複雜度的優化。比如Fibonacci數列可以優化為只使用兩個變數的額外存儲空間，0-1背包問題可以優化為O(n)的空間複雜度。
3.若進行了空間優化，則連續多次被調用時無法復用之前被調用的子結果。

最後，如果想要更全面完整的理解動態規劃，我的學習路線上只有兩步：
1. 讀一下Algrithm in C這本書的相應章節
2. 把幾個經典動態規劃問題分別用「自頂向下」和「自低向上」兩種方法實現一遍，用任何你喜歡的語言都行

：）祝開心

我在思考這個問題的意義，這裡面有個殘酷的事實。
很多人在學習的時候都希望先了解整個知識結構，再去研究具體的問題。但把這種方法套用在DP上，會發現行不通。因為DP的概念比DP的問題更難理解。能在這裡解釋DP概念的，往往都解決了幾十個或上百個DP的問題。
如果lz的提問是為了學習DP的話，我建議你先去找些DP的問題來解決，比如：動態規劃的問題，從簡單到難，做完第1頁應該就能自己總結出個梗概了。

所謂動態規劃就是站起來一邊走動一邊規劃，有效預防頸椎病……

不開玩笑，給一個「加了辣椒的菜都叫做川菜」式的回答吧（正確解釋還是應該看上面排1、2、4的答案）：

動態規劃，就是把計算過程中產生的中間結果靜態地保存起來，後面再用到這些中間結果的時候就不用再算一遍，而是直接讀取。

那明明是靜態規劃為什麼要叫動態？

其實據發明這個名字的Bellman教授講：當時他所在的公司給美國軍方打工，軍方管他們的頭頭是個大老粗，屬於那種「對『研究』、『數學』之類的辭彙有病理性的恐懼與憎惡」的那種人，於是機智的Bellman決定不告訴他自己在公司里是研究數學的。他給自己的工作安了個名稱叫「動態編程dynamic programming」（翻譯成中文時翻成了規劃）。為什麼叫「動態（dynamic）」呢？Bellman說，除了很恰當地描繪了自己的工作以外，「動態」還是一個神奇的詞：它不可能被應用於貶義的語境！你試試用它造個含貶義的句子，造不出來吧？這是一個連政客都挑不出刺的詞，所以Bellman用它給自己的研究打掩護。

找到了一個好的拓撲排序，聰明的窮舉法？

如何理解動態規劃？ - 冒泡的回答 - 知乎

我的理解是：
某個中間結果要多次用到，如果不記錄下來，需要重複計算多次。而這個重複計算從整體上會提升演算法的時間複雜度。因此我們將這些中間結果保存下來，只計算一次，需要使用時直接引用即可。
就像前面很多答案提到的「時間換空間」，這種思想在很多演算法里都可以看到。

動態規劃只是一個優化而已，它是通過保存那些已經求過值的狀態來做到的（避免了重複計算）。

很多人提到局部最優結構，但這其實不是必須的。實際情況是只要你的狀態重疊足夠多，重複對狀態求值的代價足夠高，你就應該考慮對狀態做cache。諷刺的是，動態規劃就是指這個cache的過程。基本沒太多技術含量，因為問題的根本在於狀態怎麼轉移。而我們之所以嘗試分析最優子結構，也是為了找到一個好的狀態表示（但並不是所有問題都能用所謂最優子結構來構造的）。

開一個有可能得罪所有人的玩笑：據說一個答案如果文科生看不懂，那一定不是一個好答案。

目前的答案其實已經很好了，只不過還是沒有深入到最深刻的本質。動態規劃的最根本的本質非常簡單，而且不局限於計算機演算法領域。（目前最高票的答案講得很好，但是局限於離散問題和finite horizon；其他的答案也都從不同角度講了動態規劃作為一個計算機演算法在實際應用上的一些考慮。）

動態規劃是一種思維方法，整個學科的基本思想就是一條，動態規劃之父Bellman的Principle of Optimality (翻譯成「最優化原理」？)：

設想你想要採用最優的策略解決某件事，而且這件事可以分成好多步；假設你已經知道了做這件事的整體上最優的策略；再假設你根據這個整體最優策略走了幾步，接下來剩下的幾步的你重新算了一個最優子策略，如果和整體最優策略在接下來這幾步的子策略相符合，那麼這件事符合最優化原理；然後就可以使用動態規劃的演算法解決，解決思路就是一步步找出這些最優的子策略，最後得到整體最優策略。

舉個例子：我想走最短的距離開車從(A)三藩去(B)紐約。用地圖軟體一查得到了下圖的路徑，這就是上面說的整體最優策略。我現在根據這個整體最優的路徑從三藩開了兩天到了芝加哥，然後我重新用地圖軟體查從芝加哥到紐約的最短路徑，發現和之前查到的完全重合！

（雖然第一次查的時候用到了三藩，第二次完全沒用三藩。這個發現，是不是很神奇。。。如果你覺得trivial，說明你生活經驗豐富或者腦子轉得快，但是我請你再想想，可不是所有問題都符合這個特點。。。比如，學過馬爾科夫的童鞋，你懂的。）

這就是一個符合最優化原理、從而可以被動態規劃解決的問題。

怎麼解決呢？假設我們沒有這個強大的地圖軟體，而人工地使用動態規劃演算法，那麼步驟可以是這樣的：假設所有的路徑必須經過某些驛站，首先我找到從三藩出發到每一個第一站驛站的路徑和距離，接下來計算從三藩出發到每一個第二站驛站的最短路徑（分別經過某一個相同或者不同的第一站驛站），然後計算第三站（這時候只用知道到第二站的最短路徑）、第四站（這時候只用知道到第三站的最短路徑）、最後終於算到紐約，我就知道了從三藩出發到紐約的最短路徑，於是就可以按照這個最短路徑多快好省地出發了。。。

（上圖竊取自斯坦福大學Wen Zheng老師《動態規劃》課件。）

如果關於上面這些話，你能說服自己，那麼恭喜你，你已經理解了動態規劃的靈魂。。。

動態規劃的理論意義也只有一個，就是最優化，哪怕你要解決的問題是隨機和/或混亂的。（實際意義在不同學科或應用，比如動態資產定價、計算機演算法等，可以很不一樣；也有許多豐富的內涵，目前的答案講得很好，就不班門弄斧了。）理論上雖然動態規劃可以解決符合最優化原理的問題，實際上由於curse of dimensionality等原因有很大的局限性。

最後為了不至於太過輕佻，說明一下：嚴格理解動態規劃需要學習測度論，以上試圖把動態規劃這個優美的思想用最容易理解的方式表達（連大自然都在使用動態規劃的演算法，因為大自然總是想最優化能量的分配，感興趣的可以去看看HJB方程）。

// 發現上面已經有人提到了最短路了。。但是動態規劃真的不喜歡有環的圖啊QAQ

動態規劃不是個具體的演算法，是一個框架。框架是死的，但框架里填什麼全看人。

這個框架就是有向無環圖。圖中每個點都存著一個值。你去把圖論刷一遍，弄弄拓撲排序之後，就會明白，動態規劃就是對圖中所有點執行拓撲排序，再依照拓撲序讓每個點更新自己指向的節點的值的過程。

至於圖中點怎麼定義，邊怎麼定義，值怎麼定義，「更新」怎麼定義，那就是考驗建圖論模型的能力了，我也沒能力講出個系統規律來。

這時候動態規劃那些概念都能一一對應了。所謂最優子結構就是我可以證明只要按著拓撲序來更新，保證能得到最優解。無後效性呢，就是圖不能有環。至於記憶化嘛，就是在每個點上存一個值了。遞推嘛就是把拓撲序正著來一遍，遞歸嘛就是把拓撲序反著來一遍。都沒什麼新鮮東西的。

值得一提的是，根據上述的定義，動態規劃不如最短路徑強勁（覺得不好理解的請看後面的更新）。因為最短路徑可以反覆迭代，而動態規劃必須一遍掃完。

也就是說，不要管什麼動態規划了，只要是動態規劃，最短路徑都能解：）動態規劃點裡的值嘛就是最短距離了，一個點對另一個點的更新嘛就是最短路徑的更新了。

若是連最短路徑也不能活學活使，那還是背背書讓老師開心就行了。

------------------ 更新 ------------------

對於有向無環圖，按照拓撲序更新後繼節點就是求最短路。通用的最短路演算法在此依然適用。另外，通用的最短路演算法仍然能解部分帶環的圖，所以在此可以把拓撲排序規約到最短路。當然有效率上的差別，但是我提這整個一大段只是希望用此模型輔助理解，降低學習曲線斜率而已，所以從「新的知識點越少越好」的角度，規約到最短路是最省力的了。

真寫還是要注意效率的，能用循環就循環，能遞歸+記憶化就行。別傻乎乎地建圖就行了。至於真正如何用代碼實現，循環用什麼姿勢展開能達成拓撲序，有向無環圖有沒有分層關係從而能導致用滾動數組優化空間，都是一些後面要掌握的技巧了，但是應該機械得很。

拿「背包九講」來說吧，可以嘗試給0/1背包和無限背包問題畫圖，就明白為什麼二者命令式語言實現中的循環是那麼的似是而非。其實他倆狀態圖完全不一樣，而且0/1背包的狀態更複雜。但是通過對0/1背包進行滾動數組（嚴格來講比滾動數組還變態，因為已經不是兩個數組來回滾了，是同一個數組後面覆蓋前面的）的優化，可以把存狀態的數組減少到一維，結果代碼就長得和完全背包只差一點點了。

具體點說，0/1背包的狀態是二元組(i, j)表示花費為i時，前j個元素。狀態中存值為最大能得到的利益。每個狀態出兩條邊，即第j+1個物品選還是不選。這個圖畫出來是個二維的節點陣列，有明顯的層次關係（j到j+1）。

而完全背包更簡單，狀態就是當前花費，每個狀態的出邊數和物品數相當。

順帶扯一句，這也是正則表達式中"a*"比"a{5, 81}「要好實現的原因。

至於樹狀動態規劃，那就更貼近有向無環圖的解法了，對樹的後序遍歷和拓撲排序如出一轍。

其實前面的神犇們說的很清楚了。

我稍微說說我的理解和看法：

問：什麼是dp？

答：他其實就是在有限集合上的一個遞推。

f ( new state ) = f ( old state ) + payoff ( decision ).

他其實是一個廣義有向無環圖上的最短路問題。

這個圖怎麼建立？將所有的狀態都抽象為節點。

從節點i到節點j的邊權看做是從狀態i到狀態j所作出決策後的payoff。

那麼，我們的目標狀態就是求解，從一個初始狀態到最終狀態的最短路問題。

問：怎麼實現dp？

答：兩種常用的方法。（僅僅涉及一般問題）

1. 自下而上：通過正向的loop，求出所有狀態對應的值，然後找出max或者min。

優缺點：速度慢，但是相對節省空間。

2. 自上而下：通過遞歸的方法，需要求解f(x)，則必須知道f(y)，要知道f(y)，必須求f(z).

優缺點：速度快，只用算需要的值，但是要調用堆棧，浪費空間。

問：關於複雜度的分析？

答：時間複雜度O （狀態數 * 每個狀態下所對應的決策數）。

空間複雜度O （狀態數）。

問：dp的本質？

答：把所有有影響的因素，全部加入到節點（狀態），這樣沒有影響的因素就沒能進入狀態，

從而真正意義上滿足了無後效性。接下里，就是在我們根絕上述條件所構造出的狀態圖中

做一個特殊的遞推。

遞歸 + 緩存

比如，DAG 上的最短路徑可以用遞歸定義：
$mathrm{sp}(P, P)=0$
$mathrm{sp}(P, Q)=infleft{w(P, R)+mathrm{sp}(R, Q);|;Rin mathrm{N}^{+}(P) ight}$
而且 sp 函數引用透明，因此可以用緩存來避免重複計算。

我的理解: 將中間結果保存下來, 避免重複計算, 用以提高運算效率.

猿爸爸把 1+1+1+1+1+1+1+1 = 寫在紙上，問小猿（咦）：
「它們加起來是多少哇？」

（數了一會…）「8 ！」

猿爸爸在左邊又加了個 1+，再問一次小猿：
「現在呢？」

（迅速地）「9 ！」

「為什麼小猿這麼快就知道了呢？」

「因為你剛剛加了 1 啊~」

「所以只要記得之前的結果，就不用再計一次數啦。」

嗯，動態規劃就是一種「先記住些事，方便後面節約時間」的神奇方法。

--------------------------------------------------------------------------
但是如果你覺得這個答案對你的胃口，那麼恭喜你，你對 DP 的理解成功地達到了四歲小孩的水平……FYI:
How should I explain dynamic programming to a 4-year-old?
不謝

動態規劃主要有兩個要點
狀態和轉移
滿足無後效性要求，基本就可以完成一個動態規划了

想法1)是在需要重複計算問題的時候，把之前的計算記住，減少recompute
2)新感想：如果你的DP不能不像DP,那麼你就需要加上一個維度來皆問題