選自medium
作者：Meet Zaveri
機器之心編譯
參與：曾祥極、張倩
喬治·桑塔亞納說過，“那些遺忘過去的人注定要重蹈覆轍。”這句話放在問題求解過程中也同樣適用。不懂動態規劃的人會在解決過的問題上再次浪費時間，懂的人則會事半功倍。那么什么是動態規劃？這種算法有何神奇之處？本文作者給出了初步的解答。
假設你正在使用適當的輸入數據進行一些計算。你在每個實例中都進行了一些計算，以便得到一些結果。當你提供相同的輸入時，你不知道會有相同的輸出。這就像你在重新計算之前已經計算好的特定結果一樣。
那么問題出在哪里呢？你之前計算某些結果的寶貴時間被浪費掉了。你可以通過保存之前的計算結果去輕易地解決這個問題。比如通過使用恰當的數據結構。舉個例子，你可以將輸入輸出作為鍵值對映射保存起來。
那些遺忘過去的人注定要重蹈覆轍 ~ 動態規劃
現在通過分析這個問題，我們可以將新的輸入（或者不在數據結構中的輸入）與其對應的輸出存儲下來。或者在字典中查找輸入并返回相應的輸出結果。這樣當你在進行一些計算時，你可以檢查數據結構中是否存在該輸入，如果數據輸入存在的話就可以直接獲得結果。我們將與這種方法相關的技巧稱作動態規劃。
詳解動態規劃
現在讓我們更詳細地介紹動態規劃。
簡而言之，我們可以說動態規劃主要用來解決一些希望找到問題最優解的優化問題。
一種可以用動態規劃解決的情況就是會有反復出現的子問題，然后這些子問題還會包含更小的子問題。相比于不斷嘗試去解決這些反復出現的子問題，動態規劃會嘗試一次解決更小的子問題。之后我們可以將結果輸出記錄在表格中，我們在之后的計算中可以把這些記錄作為問題的原始解。
舉個例子，斐波那契數列 0,1,1,2,3,5,8,13,…有著一個相當簡單的描述方式，它的每個數字都與前兩個緊鄰的數字相關。如果 F(n) 是第 n 個數字，那么我們會有 F(n) = F(n-1) + F(n-2)。這個在數學上稱作*遞歸方程*或者*遞推關系*。為了計算后面的項，它需要前面項的計算結果作為輸入。
大多數動態規劃問題都能被歸類成兩種類型：
大多數動態規劃問題都能被歸類成兩種類型：
- 優化問題
- 組合問題
優化問題希望你選擇一個可行的解決方案，以便最小化或最大化所需函數的值。組合問題希望你弄清楚做某事方案的數量或某些事件發生的概率。
解決方案的對比：自上而下或者自下而上
以下是兩種不同的動態規劃解決方案：
- 自上而下：你從最頂端開始不斷地分解問題，直到你看到問題已經分解到最小并已得到解決，之后只用返回保存的答案即可。這叫做記憶存儲（*Memoization*）。
- 自下而上：你可以直接開始解決較小的子問題，從而獲得最好的解決方案。在此過程中，你需要保證在解決問題之前先解決子問題。這可以稱為表格填充算法（*Tabulation，*table-filling algorithm**）。
至于迭代和遞歸與這兩種方法的關系，自下而上用到了迭代技術，而自上而下則用到了遞歸技術。
圖片中的展示在理論上可能并不完全正確，但這是一種可以理解的展示方式。
這兒有一個普通方法和動態規劃方法的比較，你可以看到兩者時間復雜度的不同。
Memoization 的準則：不要忘記
Jeff Erickson 在他的筆記中這樣描述斐波那契數列：
遞歸算法之所以速度慢，是因為它一遍又一遍地計算了相同的斐波那契數列。
來自 Jeff Erickson 筆記：http://jeffe.cs.illinois.edu/
我們可以通過記錄遞歸調用的結果來加速遞歸算法，這樣在之后需要這些結果時就不必重新算了。
Memoization 是指緩存和重用之前計算結果的技術。
如果你使用 Memoization 來解決問題，可以通過維護已經解決的子問題的映射來實現（正如我們之前討論的鍵值對映射）。你首先解決「上層」問題（通常是為了解決子問題而進行遞歸），這樣做是「自上而下」。
*memoization*的偽代碼
因此在使用遞歸的過程中，我們使用額外的內存（即這里的 lookup）來執行操作以存儲結果。如果查找命中存儲值，我們將直接返回它，或者將其添加到特定索引。
請記住，額外的內存與表格填充之間存在一個權衡。
自上而下的方法
Tabulation：以表格形式填充
但是一旦我們看到數組（存儲的解決方案）是如何被填充的，我們就可以用一個簡單的循環替換遞歸，這個循環有意地按順序填充數組，而不是依賴于復雜的遞歸來為我們完成。
來自 Jeff Erickson 的筆記：http://jeffe.cs.illinois.edu/
Tabulation 以「*自下而上*」的方式進行。它更直接，會計算所有值，但需要的開銷更少，因為它不必維護映射并以表格形式為每個值存儲數據。它還可以計算不必要的值。如果你只想計算問題的所有值，則可以使用此方法。
*tabulation*的偽代碼：
斐波那契樹的偽代碼
正如您可以在圖片中看到的偽代碼（右側），它會進行迭代（即循環直到數組結束）。它從 fib(0),fib(1),fib(2),…開始，所以使用 tabulation 方法，我們可以消除遞歸，只需通過循環元素返回結果。
追根溯源
Richard bellman 是這個概念的提出者。他在 20 世紀 50 年代中期為蘭德公司工作時想到了這一點。選擇「dynamic programming」這個名字的原因是為了隱藏他為這項研究所做的數學工作。因為他擔心他的老板會反對或不喜歡任何類型的數學研究。
所以「programming」這個詞只是一個參考，以表明這是一種老式的計劃或調度方式，通常是通過逐漸填充表格（以動態方式而不是線性方式）而不是一次全部填入的方式進行。
原文鏈接：https://medium.freecodecamp.org/an-intro-to-algorithms-dynamic-programming-dd00873362bb
