一個做太多工的遞迴
從整個計算領域裡最親切的遞迴定義開始：費氏數列，F(n) = F(n-1) + F(n-2)，其中 F(0) = 0、F(1) = 1。直接翻成程式碼，它只有兩行、而且顯然正確——你不必思考就能照定義讀出來。然而當 n 在 40 附近時它就慢如爬行，而當 n 在 90 附近時，它在你有生之年都跑不完。定義本身沒問題；出問題的是「遞迴執行它的方式」，而把這個原因精準地釘住，正是本篇導覽全部的重點。
要看清麻煩，別只是執行程式碼——把它「畫」出來，正如上一階的 遞迴樹法 教你的那樣。每一次對 F(k) 的呼叫，都會分岔成一次對 F(k-1) 與一次對 F(k-2) 的呼叫，這些分支又各自再分岔，如此下去，直到你碰到 F(1) 或 F(0)。長出來的形狀是一棵呼叫之樹，而執行時間，就是這棵樹裡節點的數目。所以真正的問題不是「遞迴有多深」，而是「它總共發出幾次呼叫」——而答案令人震驚。
看看呼叫樹，數一數重複
用手把 F(5) 的樹展開。頂端坐著 F(5)；它底下是 F(4) 與 F(3)；F(4) 底下是 F(3) 與 F(2)；如此類推。現在仔細看，醜聞立刻跳出來：F(3) 被算了兩次，F(2) 三次，F(1) 五次。這個遞迴沒有記憶——當左分支已經從頭把 F(3) 算出來時，右分支稍後跑來，又把同一個 F(3) 完全從頭再算一遍，渾然不覺。這個現象——遞迴的不同分支，需要「同一個」較小實例的答案——正是我們所說的 重疊子問題。
F(5)
|-- F(4)
| |-- F(3)
| | |-- F(2)
| | | |-- F(1)
| | | +-- F(0)
| | +-- F(1)
| +-- F(2) <-- F(2) again
| |-- F(1)
| +-- F(0)
+-- F(3) <-- the WHOLE F(3) subtree, recomputed
|-- F(2) <-- F(2) yet again
| |-- F(1)
| +-- F(0)
+-- F(1)
distinct values needed: F(0..5) -> only 6
calls actually made: 15 (and it doubles each step up)精確地數，會讓這份浪費無可抵賴。計算 F(n) 所需的呼叫次數成長得像 F(n) 自己，約莫是 1.618^n——所以工作量對 n 而言是 指數級 的。然而，總共被問過幾個「真正不同」的問題呢？只有 F(0)、F(1)，一直到 F(n)——也就是 n+1 個相異的子問題。我們付出指數級的工作量，去回答線性數量的相異問題。每一次多餘的呼叫，都是在重答一個早已解決的問題。「發出的呼叫」與「相異子問題」之間的這道落差，正是動態規劃存在所要回收的餘裕。
一句話的解法，以及它為何被允許
解藥簡單到近乎侮辱人：第一次算出每個答案時就把它記住，然後絕不算第二次。維護一張以子問題為索引的表；在重算 F(k) 之前先查表；若它已經在那裡，就立刻回傳。霎時間，n+1 個相異子問題每個都只被解一次，指數級的樹塌縮成線性量的工作，而 F(90) 一眨眼就回傳。這就是全部的想法——但說出解藥，不等於理解「它為何安全」，而這個「為何」，正是把一個小把戲與一套方法區分開來的東西。
它安全，是因為一個我們將在本階其餘部分倚賴的性質：一個子問題的答案，不取決於「你怎麼走到那裡」或「它周圍是什麼」。不論是樹的哪一個分支來問，F(3) 就是 F(3)。這是重疊子問題更深一層的兄弟，叫做 最佳子結構：一個問題的解，是由它各子問題的解所組成的，而那些子解本身在孤立狀態下也是正確的。正因為 F(3) 的值與情境無關，把它快取一次、處處重用，絕不可能給出錯誤答案——它給出的，正是遞迴本來會重算出的同一個值。
什麼時候重疊是真的，什麼時候是海市蜃樓
人們很容易下結論說每個遞迴都會重複做工，但那是錯的，而這個對比值得去體會。把同樣的呼叫樹練習，套在分治那一階的 合併排序 上：它把陣列切成兩半並遞迴，但左半與右半是「不同的陣列」。沒有任何子問題被問過第二次；它遞迴樹的每個節點，都是全新的、未曾見過的實例。這正是為什麼分治遞迴在完全不快取任何東西的情況下就能已然高效——根本沒有重複的工作可回收。
所以診斷的問題很精確：當遞迴分岔時，不同的分支是否曾落在「完全相同」的子問題上？對費氏數列而言，F(k) 由單一個數 k 標定，而 k 活在 0..n 這個小範圍裡，所以碰撞是被強迫發生的——鴿籠原理保證分支必定會重用同一個 k。對合併排序而言，子問題由一個對它的路徑而言獨一無二的子陣列標定，所以碰撞永不發生。重疊的有無，是子問題「如何被命名」的性質：當不同的路徑能命名出同一個子問題時，你就有重疊；當每條路徑都命名出新東西時，你就沒有。
本階要往哪裡去
你現在已經以最純粹的形式遇見了那個創始的觀察，而本階其餘的部分，就是由它衍生而來的工程。要確保每個子問題只被解一次，有兩條路。第一條保留自然的遞迴，但給它栓上一個快取，第二次請求時回傳已存的答案——那就是 由上而下的記憶化，是下一篇導覽的主題，也是從你已經寫出的那個慢遞迴出發、最溫和的一步。第二條把遞迴丟掉，按一個謹慎的順序、最小的子問題優先，直接把表填滿——那就是 由下而上的製表。
從那裡開始，技藝層層疊加：精確地命名狀態、寫出由較小答案建構較大答案的轉移、選一個評估順序使每個格子在被需要之前就備妥，以及最後透過回溯整張表來 重建真正的解——而不只是它的成本。手握這些工具，下一階那些看似困難的經典問題——0/1 背包問題、最長共同子序列、兩個字串間的編輯距離——全都臣服於你剛才看著它拯救費氏數列的那同一個有紀律的想法。
臨走前一個誠實的提醒：把指數級塌縮成線性是那個戲劇性的案例，但動態規劃不會讓所有東西都變便宜，只會讓它便宜到「相異狀態的數目，乘上每個狀態的工作量」這個程度。如果一個問題真的擁有指數級多的「相異」子問題——不是重複，而是真正不同的——那麼任何快取都救不了你，因為根本沒有東西可重用。動態規劃之所以強大，正是當相異子問題的數目很小的時候；它的極限，恰恰就是這個數目的極限。