今天咱們來聊聊動態規劃。
動態規劃(dynamic programming)是一種基礎的算法設計思想。作為一種尋找最優解的通用方法，它是在20世紀50年代由美國數學家Richard Bellman（也就是之前最短路徑問題中Bellman ford算法的發明者之一）所發明的。
動態規劃的思想實質是分治思想和解決冗餘。
與分治法類似的是，我們將原問題分解成若干個子問題，先求解子問題，再從這些子問題的解得到原問題的解。
與分治法不同的是，經分解的子問題往往不是互相獨立的。若用分治法來解，有些共同部分被重複計算了很多次。如果能夠保存已解決的子問題的答案，在需要時再查找，這樣就可以避免重複計算、節省時間，也就是解決冗餘。
實際應用中嘗試解決一個問題時，其實就是在思考如何將這個問題表達成狀態（用哪些變量存儲哪些數據），以及如何在狀態中轉移（怎樣根據一些變量計算出另一些變量）。
什麼是狀態？我們在接下來的例子中體會這個概念。
以Fibonacci數列為例，每一個Fibonacci數就是這個問題的一個狀態，每求一個新數字只需要之前的兩個狀態。這種狀態計算很直接，只需要依照固定的模式從舊狀態計算出新狀態就行（a[i]=a[i-1]+a[i-2]），不需要考慮是不是需要更多的狀態，也不需要選擇哪些舊狀態來計算新狀態。
求Fibonacci數列的例子過於簡單，為了解決更複雜的問題，我們還需要引入階段的概念。
階段是指隨著問題的解決，在同一個時刻可能會得到的不同狀態的集合。
在Fibonacci數列中，每一步會計算得到一個新數字，在這裡每一步就是一個階段，而每個階段只有一個狀態（所以我們會忽略階段的概念）。
我們再以深度優先搜索走迷宮的過程為例：每一步只能走一格，因為可以向另外三個方向走，所以每一步可能會處於很多個不同的位置。從頭開始走了幾步就是第幾個階段，每一步可能處於的位置稱為一個狀態，下一步可能到達的位置的集合就是這個階段下所有可能的狀態。
整理一下，假如問題有n個階段，每個階段都有多個狀態，不同階段的狀態數不必相同，一個階段的一個狀態可以得到下個階段的所有狀態中的幾個。而我們要求的解一般就是最終階段的某個狀態。
了解了階段、狀態的概念後，我們發現，劃分階段、定義狀態其實就相當於在劃分子問題，也就是在遵循分治思想。
而動態規劃有別於其他算法的關鍵在於解決冗餘。
我們對問題進行分類，然後針對動態規劃能解決的問題進行說明，了解它是如何解決冗餘的：
每個階段只有一個狀態->遞推；
每個階段的最優狀態都是由上一個階段的最優狀態得到的->貪心；
每個階段的最優狀態是由之前所有階段的狀態的組合得到的->搜索；
每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到而不管之前這個狀態是如何得到的->動態規劃。
在這個分類中我們也可以看出：一個問題是該用遞推、貪心、搜索還是動態規劃，完全是由這個問題本身階段間狀態的轉移方式（也就是得出下一個狀態的方式）決定的。
重點看有關動態規劃的部分。在這個闡述中，每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到（特別是與後面的階段無關），包含了兩種性質：最優子結構（問題的最優解所包含的子問題的解也是最優的）和重疊子問題（子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到）；而不管之前這個狀態是如何得到的，這個性質叫做無後效性。
還是以Fibonacci數列為例。在計算到第100項的時候，需要用到第99項和98項（最優子結構，重疊子問題）。這時候你還需要重新計算第99項嗎？
不需要，你只需要在第一次計算的時候把它記下來就可以了（無後效性）。
在要用到第99項時，如果沒有計算過，就按照遞推式計算；如果計算過，直接使用，就像把第99項存儲在一個緩存區裡一樣，這種方法，叫做「記憶化」，是遞推式求解的技巧。這種技巧，通俗的說叫「花費空間來節省時間」：動態規劃就是通過這樣的方式「記憶」過去，節省每次重新計算的時間。
我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這是動態規劃法的基本思路。具體的動態規划算法多種多樣，但它們具有相同的填表格式。
我們將這個表稱為最優決策表。最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關係依次填寫，最後根據整個表格的數據通過簡單的取捨或者運算求得問題的最優解。
再以最長遞增子序列問題為例。
對於長度為N的數組A[n] = {a[0], a[1], a[2], ..., a[n-1]}，將以a[j]結尾的最大遞增子序列長度設為L[j]，那麼狀態轉移方程為：
L[j] = max(L[i]) + 1）, 0<=i<j
我們對每一個A[n]中的元素都計算以他們各自結尾的最大遞增子序列的長度，想求a[j]結尾的最大遞增子序列的長度時，我們就需要遍歷j之前的所有位置i，找出a[i] < a[j]，計算這些i中，能產生最大L[i]的i，之後就可以求出L[j]。我們要求的問題——數組A的最大遞增子序列的長度，就是L[n-1]。
在這個問題中，計算每一個L[i]的過程就是一個階段，對每一個以a[i]為結尾的子序列的長度就是該階段的一個狀態。我們只需要求出每個階段的一個最優狀態，計入表格，就可以一步步得出最終狀態，而不需要每次都循環尋找一個遞增子序列。
所以，尋找符合「最優子結構」的狀態和狀態轉移方程的定義就是我們在利用動態規劃解決問題時要做的。在找到之後，這個問題就可以以「記憶化地求解遞推式」的方法來解決。而尋找到的定義，才是動態規劃的本質。
需要注意的是，一個問題可能有多種不同的狀態定義和狀態轉移方程定義，即使存在一個有後效性的定義，也不代表該問題一定不適用於動態規劃。
總結一下解決問題的具體步驟：
(1)劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態和狀態變量：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
(3)確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯繫，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。
(4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
我們再用動態規劃的方法具體解決一個問題：背包問題。