動態規劃入門
摘要：動態規劃算法通常這樣利用重疊子問題性質：對每個子問題求解一次，將解存入一個表中，當再次需要這個子問題時直接查表，每次查表的代價爲常量時間。適合用動態規劃方法求解的最優化問題應該具備的第二個性質是子問題空間必須足夠“小”，即問題的遞歸算法會反覆地求解相同的子問題，而不是一直生成新的子問題。
動態規劃（dynamic programming）與分治方法相似，都是通過組合子問題的解來求解原問題（在這裏，“programming”指的是一種表格法，並非編寫計算機程序）。
分治方法將問題劃分爲互不相交的子問題，遞歸地求解子問題，再將它們的解組合起來，求出原問題的解。
動態規劃應用於子問題重疊的情況，即不同的子問題具有公共的子子問題（子問題的求解是遞歸進行的，將其劃分爲更小的子子問題）。
在這種情況下，分治算法會做許多不必要的工作，它會反覆地求解那些公共子問題。
動態規劃算法對每個子子問題只求解一次，將其解保存在一個表格中，從而無需每次求解一個子子問題時都重新計算，避免了不必要的計算工作。
動態規劃方法通常用來求解最優化問題（optimization problem）。
設計一個動態規劃算法的步驟：
-
刻畫一個最優解的結構特徵。
-
遞歸地定義最優解的值。
-
計算最優解的值，通常採用自底向上的方法。
-
利用計算出的信息構造一個最優解。
算法原理
適合應用動態規劃方法求解的最優化問題應該具備的兩個要素：最優子結構和子問題重疊。
最優子結構
用動態規劃方法求解最優化問題的第一步就是刻畫最優解的結構。如果一個問題的最優解包含其子問題的最優解，則稱此問題具有 最優子結構 性質。因此，某個問題是否適合應用動態規劃算法，它是否具有最優子結構性質是一個好線索。
發掘最優子結構性質的通過模式
-
證明問題最優解的第一個組成部分是做出一個選擇。做出這次選擇會產生一個或多個待解的子問題。
-
對於一個給定問題，在其可能的第一步選擇中，你假定已經知道哪種選擇纔會得到最優解。你現在並不關心這種選擇具體是如何得到的，只是假定已經知道了這種選擇。
-
給定可獲得最優解的選擇後，你確定這次選擇會產生哪些子問題，以及如何最好地刻畫子問題空間。
-
利用“剪切-粘貼”（cut-and-paste）技術證明：作爲構造原問題最優解的組成部分，每個子問題的解就是它本身的最優解。證明這一點是利用反證法：假定子問題的解不是其自身的最優解，那麼我們就可以從原問題的解中“剪切”掉這些非最優解，將最優解“粘貼”進去，從而得到原問題一個更優的解，這與最初的解是原問題最優解的前提假設錨段。
一個刻畫子問題空間的好經驗是：保持子問題空間儘可能簡單，只在必要時才擴展它。
對於不同問題領域，最優子結構的不同體現在兩個方面：
-
原問題的最優解中涉及多少個子問題，以及
-
在確定最優解使用哪些子問題時，我們需要考察多少種選擇。
可以用子問題的總數和每個子問題需要考察多少種選擇這兩個因素的乘積來粗略分析動態規劃算法的運行時間。
在動態規劃方法中，通常自底向上地使用最優子結構。也就是說，首先求得子問題的最優解，然後求原問題的最優解。在求解原問題過程中，我們需要在涉及的子問題中做出選擇，選出能得到原問題最優解的子問題。原問題最優解的代價通常就是子問題最優解的代價加上由此次選擇直接產生的代價。
能夠使用貪心算法的問題也必須具有最優子結構性質。貪心算法和動態規劃最大的不同在於，它並不是首先尋找子問題的最優解，然後在其中進行選擇，而是首先做出一次“貪心”選擇—在當時（局部）看來最優的選擇—然後求解選出的子問題，從而不必費心求解所有可能相關的子問題。
|
Note |
問題：使用貪心算法和動態規劃的界線是什麼？什麼時候使用貪心？什麼時候使用動態規劃？ |
重疊子問題
適合用動態規劃方法求解的最優化問題應該具備的第二個性質是子問題空間必須足夠“小”，即問題的遞歸算法會反覆地求解相同的子問題，而不是一直生成新的子問題。
如果遞歸算法反覆求解相關的子問題，則就稱爲最優化問題具有 重疊子問題（overlapping subproblems） 性質。
與之相對的，適合用分治算法求解的問題通常在遞歸的每一步都生成全新的子問題。
動態規劃算法通常這樣利用重疊子問題性質：對每個子問題求解一次，將解存入一個表中，當再次需要這個子問題時直接查表，每次查表的代價爲常量時間。
一個問題是否適合用動態規劃求解同事依賴於子問題的無關性和重疊性。兩個子問題如果不共享資源，它們就是獨立的。而重疊是指兩個子問題實際上是同一個子問題，只是作爲不同問題的子問題出現而已。
將自頂向下的遞歸算法（無備忘錄）與自底向上的動態規劃算法進行比較，後者要高效得多，因爲它利用了重疊子問題性質。
重構最優解
從實際考慮，通常將每個子問題所做的選擇存在一個表中，這樣就不必根據代價來重構這些信息。
備忘
可以保持自頂向下策略，同時達到與自底向上動態規劃方法相似的效率。思路就是對自然但低效的遞歸算法加入備忘機制。維護一個表記錄子問題的解，但仍然保持遞歸算法的控制流程。
帶備忘的遞歸算法爲每個子問題維護一個表項來保存它的解。每個表項的初值設爲一個特殊值，表示尚未填入子問題的解。當遞歸調用過程中第一次額遇到子問題時，計算其解，並存入對應表項。隨後每次遇到同一個問題，只是簡單地查表，返回其解。
|
Tip |
一個更通用的備忘方法是使用散列技術，以子問題參數爲關鍵字。 |
通常情況下，如果每個子問題都必須至少求解一次，自底向上動態規劃算法會比自頂向下備忘算法快，因爲自底向上算法沒有遞歸調用的開銷，表的維護開銷也更小。而且，對於某些問題，可以利用表的訪問模式來進一步降低時空代價。相反，如果子問題空間中的某些子問題完全不必求解，備忘方法就會體現出優勢了，因爲它只會求解那些絕對必要的子問題。
