從開口要答案到主動填表
上一篇你把那個會浪費地重算重疊子問題的天真遞迴，用記憶化馴服了：你保留遞迴的形狀，但在第一次算出每個答案的當下就把它停進一個快取，於是同一子問題的第二次請求就成了免費的查表。製表法（也叫由下而上的動態規劃）則從相反的方向抵達同一個終點。你不再讓遞迴去「開口要」子問題、在途中才發現自己需要哪些，而是事先坐下來，把每個子問題都列出來，並以一種「每個答案在你需要它時恰好已經就緒」的順序，把它們的答案填進去。
拿費氏數列來說，它是本階開頭的玩具例子。記憶化算 F(n) 的方式是一路遞迴下降到 F(1) 和 F(0)，再在回升的途中快取。製表法把它翻過來：開一個陣列 fib[0..n]，親手寫下 fib[0]=0 與 fib[1]=1，然後讓一個迴圈從 i=2 往上掃，計算 fib[i]=fib[i-1]+fib[i-2]。每一格只讀它左邊的格子，而那些都已經填好了。沒有遞迴、沒有呼叫堆疊、沒有快取未命中的檢查——只是一個迴圈走過一張表。這就是製表法的全部精神：用一張明確的表格和一個明確的填表順序，取代遞迴。
fib[0] = 0
fib[1] = 1
for i = 2 to n:
fib[i] = fib[i-1] + fib[i-2] # left-to-right: deps ready
return fib[n]你必須釘死的三件事
製表法不是自由發揮；它逼你把三個決定講明白，而這三個決定記憶化容許你含糊帶過。第一，表格形狀：幾個維度、各多大——一個以 i 索引的陣列、一個以 (i, j) 索引的二維格子，諸如此類。第二，基底情況：那些因為不依賴任何東西、所以你親手填的格子。第三，也是初學者最容易被咬到的，計算順序：你走訪格子的次序，要使你在計算某格時，它所讀的每一格都已經算完。
第三點是製表法的核心，值得一幅清晰的圖像。把每個子問題想成一個節點，並且每當「計算 A 需要用到 B 的答案」時，就從子問題 A 畫一個箭頭指向子問題 B。這是一張依賴圖，而因為子問題永遠只依賴「更小的」子問題，這張圖沒有環——它是一個有向無環圖。於是一個有效的計算順序，恰好就是這張有向無環圖的一個拓樸排序：只在某節點所指向的一切都完成後，才去走訪它。對費氏數列來說，這張有向無環圖是一條線，拓樸順序就單純是 0, 1, 2, ..., n——這正是為什麼一個樸素的由左而右迴圈就管用。
二維走一遍：數格子路徑
讓我們填一張真正的二維表。在一個 m 乘 n 的格子裡，數從左上角走到右下角、且只能向右或向下走的路徑數。定義狀態 ways[i][j] = 抵達格子 (i, j) 的這種路徑的數目。一條路徑要抵達 (i, j)，不是從 (i-1, j) 向下踏一步，就是從 (i, j-1) 向右踏一步，所以轉移式是 ways[i][j] = ways[i-1][j] + ways[i][j-1]。基底情況是最上面一列和最左邊一行，那裡恰好只有一條路徑（一直走直線），所以那裡每一格都是 1。
現在談順序。格子 (i, j) 讀的是正上方那格和正左方那格，所以當我們抵達 (i, j) 時，這兩格都必須已經填好。一個逐列掃描——外層迴圈 i 由上而下，內層迴圈 j 由左而右——恰好滿足這點：等我們碰到 (i, j) 時，第 i-1 列已經整列完成，而 (i, j-1) 在同一列裡早一步就完成了。那個巢狀迴圈「就是」這張格子依賴有向無環圖的一個拓樸順序。把它跑在一個 3 乘 3 的格子上，內部會填成 1,1,1 / 1,2,3 / 1,3,6——右下角的答案是 6 條路徑，你可以親手驗證。
重建答案，並把表格縮小
一張填好的表通常給你的是最佳值——那個計數、成本、長度——但你往往想要實際的物件：那條路徑、被選的物品、對齊好的字串。標準的做法是在填完的表上靠回溯重建解。從答案那格出發，每一步都看轉移式：這個值是從哪個前驅格子來的？走到那個前驅，再重複，直到碰上一個基底情況。你描出的這條軌跡，反轉過來，就是解。在上面的格子裡，你會從右下角反覆踏向它所加總的那個（上）或（左）的來源，從而還原出一條具體的路徑。
製表法還暴露出一個由上而下會藏起來的記憶體優化。因為格子的轉移式永遠只讀「前一列」（以及當前列左邊的部分），你不必同時把全部 m 列都放在記憶體裡——兩列、甚至小心地原地更新一列，就夠了。這把空間從 O(m*n) 降到 O(n)，而時間仍是 O(m*n)。這個「滾動陣列」技巧是由下而上的招牌優勢：當依賴觸及的範圍很淺時，你可以把表格的舊層丟掉。代價要誠實講清楚、也值得一講：一旦你壓扁了表格，就丟掉了重建所需的歷史，所以只有在必須還原物件本身時，你才保留完整的表。
由下而上何時勝、何時敗
製表法和記憶化計算的是同一張有向無環圖，所以它們的漸進時間完全相同：兩者的總時間都是（相異子問題的數目）乘以（每次轉移的工作量）。不同的是常數和失敗模式。由下而上通常在常數因子上勝出——一個對陣列的緊湊迴圈沒有遞迴開銷、沒有呼叫堆疊、沒有雜湊表的快取查找，記憶體存取模式也更友善。它也不會撐爆呼叫堆疊，而很深的遞迴會。而且，如我們剛看到的，它打開了滾動陣列省空間的大門。
但由下而上有一個真實的代價，是由上而下悄悄避開的：製表法會填表格裡的「每一」格，不管最終答案是否依賴它。記憶化只會計算遞迴實際觸及到的子問題。如果可達的子問題只是整張表的稀疏一小撮——在硬幣找零、或重量很彆扭的背包問題裡是常見情況——由上而下在實務上可以快上許多，即使兩者是相同的大O，因為大O算的是最壞情況，恰恰把這種常數藏了起來。當表格被密集地需要時（費氏數列、格子路徑、編輯距離），製表法是自然的選擇；當它只被稀疏地需要時，記憶化能省下那些被浪費的格子。
還有一個由下而上特有的正確性陷阱，值得直說：一個製表法只有在你的迴圈順序是依賴有向無環圖一個貨真價實的拓樸順序時才正確。把順序弄錯——某個維度迭代方向反了，或在某格所讀的格子之前就填了它——程式照樣會跑、會回傳一個數字、而且默默地錯。記憶化在這點上比較寬容，因為它在第一次被問到時才按需計算某個依賴。所以讓由下而上安全的那條唯一紀律，正是本篇講的：寫出轉移式、辨明每格會讀什麼、並把迴圈排成讓讀取永遠指向後方已填好的格子。