動态規劃

動态規劃不是某一種具體的算法，而是一種算法思想

動态規劃（英語：dynamic programming，簡稱 dp）是一種在數學、管理科學、計算機科學、經濟學和生物資訊學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

動态規劃不是某一種具體的算法，而是一種算法思想：

若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。

應用這種算法思想解決問題的可行性，對子問題與原問題的關系，以及子問題之間的關系這兩方面有一些要求，它們分别對應了最優子結構和重複子問題。

動态規劃的背景

最優子結構規定的是子問題與原問題的關系

動态規劃要解決的都是一些問題的最優解，即從很多解決問題的方案中找到最優的一個。當我們在求一個問題最優解的時候，如果可以把這個問題分解成多個子問題，然後遞歸地找到每個子問題的最優解，最後通過一定的數學方法對各個子問題的最優解進行組合得出最終的結果。總結來說就是一個問題的最優解是由它的各個子問題的最優解決定的。

重複子問題規定的是子問題與子問題的關系。

當我們在遞歸地尋找每個子問題的最優解的時候，有可能會會重複地遇到一些更小的子問題，而且這些子問題會重疊地出現在子問題裡，出現這樣的情況，會有很多重複的計算，動态規劃可以保證每個重疊的子問題隻會被求解一次。當重複的問題很多的時候，動态規劃可以減少很多重複的計算。

重複子問題不是保證解的正确性必須的，但是如果遞歸求解子問題時，沒有出現重複子問題，則沒有必要用動态規劃，直接普通的遞歸就可以了。

例如，斐波那契問題的狀态轉移方程 f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2)。在求 f(5)f(5) 時，需要先求子問題 f(4)f(4) 和 f(3)f(3)，得到結果後再組合成原問題 f(5)f(5) 的解。遞歸地求 f(4)f(4) 時，又要先求子問題 f(3)f(3) 和 f(2)f(2) ，這裡的 f(3)f(3) 與求 f(5)f(5) 時的子問題重複了。

解決動态規劃問題的核心：找出子問題及其子問題與原問題的關系

找到了子問題以及子問題與原問題的關系，就可以遞歸地求解子問題了。但重疊的子問題使得直接遞歸會有很多重複計算，于是就想到記憶化遞歸法：若能事先确定子問題的範圍就可以建表存儲子問題的答案。

動态規劃算法中關于最優子結構和重複子問題的了解的關鍵點：

證明問題的方案中包含一種選擇，選擇之後留下一個或多個子問題

設計子問題的遞歸描述方式

證明對原問題的最優解包括了對所有子問題的最優解

證明子問題是重疊的（這一步不是動态規劃正确性必需的，但是如果子問題無重疊，則效率與一般遞歸是相同的）