拒絕遺忘：高效的動態規劃演演算法

（點選上方快速關註並設定為星標，一起學Python）

來源：機器之心  作者：Meet Zaveri  連結：

https://mp.weixin.qq.com/s/lEm3cIjHwIwRMow1eBdZlw

 

喬治·桑塔亞納說過，“那些遺忘過去的人註定要重蹈覆轍。”這句話放在問題求解過程中也同樣適用。不懂動態規劃的人會在解決過的問題上再次浪費時間，懂的人則會事半功倍。那麼什麼是動態規劃？這種演演算法有何神奇之處？本文作者給出了初步的解答。

假設你正在使用適當的輸入資料進行一些計算。你在每個實體中都進行了一些計算，以便得到一些結果。當你提供相同的輸入時，你不知道會有相同的輸出。這就像你在重新計算之前已經計算好的特定結果一樣。

那麼問題出在哪裡呢？你之前計算某些結果的寶貴時間被浪費掉了。你可以透過儲存之前的計算結果去輕易地解決這個問題。比如透過使用恰當的資料結構。舉個例子，你可以將輸入輸出作為鍵值對對映儲存起來。

那些遺忘過去的人註定要重蹈覆轍 ~ 動態規劃

現在透過分析這個問題，我們可以將新的輸入（或者不在資料結構中的輸入）與其對應的輸出儲存下來。或者在字典中查詢輸入並傳回相應的輸出結果。這樣當你在進行一些計算時，你可以檢查資料結構中是否存在該輸入，如果資料輸入存在的話就可以直接獲得結果。我們將與這種方法相關的技巧稱作動態規劃。

詳解動態規劃

現在讓我們更詳細地介紹動態規劃。

簡而言之，我們可以說動態規劃主要用來解決一些希望找到問題最優解的最佳化問題。

一種可以用動態規劃解決的情況就是會有反覆出現的子問題，然後這些子問題還會包含更小的子問題。相比於不斷嘗試去解決這些反覆出現的子問題，動態規劃會嘗試一次解決更小的子問題。之後我們可以將結果輸出記錄在表格中，我們在之後的計算中可以把這些記錄作為問題的原始解。

舉個例子，斐波那契數列 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