動態規劃

在 「愚公移山與遞迴」 一篇當中談到 exhaustive search 類問題。 其實此類問題, 未必都真的需要用愚公移山的方式來解。 有一部分看似需要用遞迴解的問題, 其實可以用更有效率的 動態規劃 dynamic programming 演算法來解。

最長共同子序列

研究物種演化關係的生物學家, 比對不同物種的 DNA 到底有多麼接近, 據此可以建立出 phylogenetic tree。 我們研究這個問題的簡化版: Longest Common Subsequence 最長共同子序列 問題: 找出 X 與 Y 兩個序列最長的共同部分, 例如:
X = (A G C T A T A C G A T G A C T)
Y = (G T C A G T A T A G T C A T A T G)
這兩個序列最長的共同部分, 就是:
G C T A T A G A T A T

構想一: 大不了將 X 的所有子序列找出來, 逐一檢查看看 X 的每個子序列是否也是 Y 的子序列。 ==> 用遞迴解。 Q: 試寫一個遞迴程式, 產生 X 的所有子序列。

構想二: 我們設法將原問題拆成幾個小一號, 但與原問題類似的問題。 假設輸入資料為 X = (x(1),x(2),...x(m)) 及 Y = (y(1),y(2),...y(n)) 兩個序列。 "X 與 Y 的尾巴元素是否相同? x(m) == y(n) 嗎?" 我們根據這個問題的所有可能答案 (其實只有兩種可能) 分項來討論。

  1. 若尾巴相同, 那麼顯然這個共同的尾巴會出現在 LCS 的尾巴。 所以可以把 X 的尾巴切掉得到 X', 又把 Y 的尾巴切掉得到 Y', 求 X' 與 Y' 的 LCS, 然後在這個 LCS 的尾巴接上 x(m) (也就是 y(n)) 就可以了。
  2. 若尾巴不同, 那麼這兩個尾巴元素不可能同時對 LCS 都有貢獻。 改求 X' 與 Y 的 LCS, 及 X 與 Y' 的 LCS, 兩者之中必然有一個就是我們要的答案。

==> 構想二還是用遞迴解。 如果我們寫一個遞迴程式 lcs 計算最長共同子序列的長度, 其中最核心的工作將是:

        int lcs(char *x, char *y) {
            ...
            if (x[0] == y[0])
                return lcs(x+1, y+1) + 1;
            else {
                a = lcs(x, y+1);
                b = lcs(x+1, y);
                return a > b ? a : b;
            }
            ...
        }

這裡我們順著 c 語言的規定 (字串尾巴固定是 '\0') 遞迴時採取截頭, 而非去尾, 但觀念是一樣的。

                              A...ACT
                         /----G...ATG----\
                         |               |
                       A...AC          A...ACT
                   /---G...ATG--\      G...AT
                   |            |          |
                 A...A        A...AC       |
              /--G...ATG--\ /-G...AT-----\ |
              |           | |            | |
             A...        A...A          A...AC
             G...ATG     G...AT         G...A

如果真的用這個演算法去解, 會花蠻多時間的, 這個問題應該放到 「愚公移山與遞迴」 那一章去討論。 但我們注意到遞迴時, 不同的子問題會 重複地問相同的孫問題, 非常浪費。 例如上圖當中的 lcs("A...A", "G...AT") 與 lcs("A...AC", "G...A") 都各被問了兩次。 何不改採由下而上的順序解題: 先解孫問題, 把答案存在表格裡, 然後再解子問題, 最後才解父問題? 這樣當子問題需要孫問題的答案時, 直接查表即可, 不論孫問題被查詢多少次, 都不會再重複計算, 省下許多時間。 於是得到一個動態規劃類的演算法 lcs 範例程式 。

除了記載最長共同子序列的 長度 之外, 還要記取每步截短問題時, 究竟選取那一個子問題的答案來當做本問題的基礎。 在 lcs 範例程式 當中, path 陣列的功用正是如此。 最後可藉著 path 陣列一路往回走, 方可找出最長共同子序列。 走斜角方向的步驟, x, y 兩序列該元素相同, 也正是共同子序列的一部分。 走垂直或水平方向的則對共同子序列沒有貢獻。 動態規劃版的 LCS, 所使用的表格大小 O(mn), 耗時 O(mn)。

背包問題

背包問題 knapsack problem: 有 n 種物品 x(1), x(2), ...x(n), 其價值與重量各為 v(i) 與 w(i) (i=1,2,...n), 其中所有的 w(i) 均為整數。 如何搭配選取這 n 種物品, 使得選出的物品價值最高, 但總重量不超過負重限制 m? 例如 m=23, n=5, 各種物品的價值與重量分別為:

品名 x(i) A B C D E
價值 v(i) 19 24 33 45 50
重量 w(i) 5 6 8 11 12
限量 c(i) 6 6 5 1 1

背包問題其實有好幾個版本:

範例程式 knapsack 裡面有兩個版本: ks_ul (修改自 Sedgewick 書中程式) 是無限量供應版; ks_count 是第一種 (彈性最大, 最麻煩的) 限量供應版。

先看較簡單的無限量版 integral knapsack。 想解決這個問題, 我們先自問一個簡單的問題: 最佳解裡面, 究竟有沒有取 x(n)? 只有兩種可能:

  1. 有。 那麼何妨請另外一位頭腦比我們發達, 四肢比我們簡單, 僅能負重 m-w(n) 的人, 來幫我們解決小一號的問題? 等他將他的背包以最佳方式填滿之後, 我們再將 x(n) 放進去, 就是我們的最佳解了。
  2. 沒有。 那麼 x(n) 的存在, 不過是在擾亂我們的心智, 其實一點用處也沒有。 不如當做 x(n) 根本不存在, 直接解小一號的問題: "只有 x(1) ... x(n-1) 可選取, 負重限制為 m"。

如果在解 "有 x(1) ... x(n) 可選取, 負重限制為 m" 的問題時, 已有上述問題的答案, 就只需要查表。 從這裡可以看出應如何製作表格。 定義 P(i,j) 為這個問題: "有 x(1) ... x(j) 可選取, 負重限制為 j"。 我們將 P(i,j) 的答案, 放在第 i 列, 第 j 行, 由上而下, 由左而右, 逐一填表, 得到以下演算法:

        for (每多一種物品 x(j) 加入可選擇行列) {
            for (由小而大考慮負重限制為 i 的小一號問題) {
                if (value[i] < value[i-w[j]] + v[j]) {
                    value[i] = value[i-w[j]] + v[j];
                    last[i] = j;
                }
            }
        }

                           * (少一種物品可選)
                           |
                           v
                * -------->*
              (負重稍輕)   (要解的問題)
   --- .. -- 5-------------10-------------15-------------20-------------25
 A:  0 .. 0 19 19 19 19 19 38 38 38 38 38 57 57 57 57 57 76 76 76 76 76 95
     - .. -  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A
 B:  0 .. 0 19 24 24 24 24 38 43 48 48 48 57 62 67 72 72 76 81 86 91 96 96
     - .. -  A  B  B  B  B  A  B  B  B  B  A  B  B  B  B  A  B  B  B  B  B
 C:  0 .. 0 19 24 24 33 33 38 43 48 52 57 57 66 67 72 76 81 85 90 91 99100
     - .. -  A  B  B  C  C  A  B  B  C  C  A  C  B  B  C  C  C  C  B  C  C
 D:  0 .. 0 19 24 24 33 33 38 45 48 52 57 57 66 69 72 78 81 85 90 93 99102
     - .. -  A  B  B  C  C  A  D  B  C  C  A  C  D  B  D  C  C  C  D  C  D
 E:  0 .. 0 19 24 24 33 33 38 45 50 52 57 57 66 69 74 78 83 85 90 95100102
     - .. -  A  B  B  C  C  A  D  E  C  C  A  C  D  E  D  E  C  C  E  E  D
   --- .. -- 5-------------10-------------15-------------20-------------25

注意表格畫出來雖然是二維的, 但程式裡面其實只用到兩個一維陣列。 計算 "至 x(i) 可拿" 問題時, 只需要參考到 "至 x(i-1) 可拿" 的答案; 更早的答案並不需要, 所以不必記住。

至於最後究竟應該取那這樣物品才會達成最佳解, 只要沿著 last 陣列倒退找即可。 因為 last[m] 記載著最後取的那件物品, 如果將它從背包取出不算, 那麼剩下來的 (其他該取的) 物品, 可以從 "負重限制 m-w[last[m]] 問題" 的解答裡讀出來, 依此類推... 以上例來說, 從表格的 E-25 當中讀出最後取的物品為 D; 於是倒退回去查 E-14 讀出 C; 再查 E-6 讀出 B。 所以最佳解為 D,C,B。 又例如 m=21 呢? 從 E-21 讀出 C; 於是倒退回去查 E-13 讀出 C; 再查 E-5 讀出 A。 所以最佳解為 C,C,A。

為什麼都是查 e 那一列呢? 如果最後拿的不是 e, 本來應該向上查而不是向左查呀? 其實向左查, 會發現它的答案根本就是從上面抄下來的。 所以兩種查法都正確; 但若向上查, 則陣列空間無法重複使用, 必須真的使用二維陣列; 向左查, 則舊的資料就可以直接丟棄不用, 比較節省演算法的空間。

表格使用空間為 O(m); 整個演算法耗時 O(mn)

接下來看限量供應版。 最後一件物品所取的不是 x(n), 未必就表示完全不取 x(n) -- 有可能因為 x(n) 已經取光了。 也可能因此而必須回頭取從前考慮過的其他類物品, 如 x(1),x(2),... 到 x(n-1) 呀! 我們改問另外一句話: 如果從最佳解裡面刪除一件物品的話, 得到的會是那一個 (小一號) 問題的最佳解? 如果從最佳解的袋中刪除一件物品 x(i), 得到的應該是 「負重限制為 m-w(i)」 的最佳解。 所有可能刪除的物品完全試過一遍之後, 也就將原問題的所有可能性尋遍了。 當然也有最後一種可能: 根本就沒有 「可能刪除的物品」 -- 因為負重限制太低, 連最輕的東西都拿不起。 這樣的想法會造成某些答案重複考慮, 不過這無傷大雅, 大不了降低一點效率; 重點是不可以有遺漏。 於是必須修改建表的順序, 兩層迴圈的內外關係對調過來, 得到不同的表格:

                           * (負重稍輕)
                           |
                           v
        *       *          *
        |       |          ^
        |  ...  |          |
        -------------------/
           (少取一件物品)

    val/lim | bi  A  B  C  D  E     95/ 23 |  D  0  0  0  1  1
      0/  1 |  -  0  0  0  0  0     99/ 24 |  C  0  0  3  0  0
      0/  2 |  -  0  0  0  0  0    102/ 25 |  A  1  0  1  0  1
      0/  3 |  -  0  0  0  0  0    107/ 26 |  B  0  1  1  0  1
      0/  4 |  -  0  0  0  0  0    111/ 27 |  C  0  0  2  1  0
     19/  5 |  A  1  0  0  0  0    116/ 28 |  C  0  0  2  0  1
     24/  6 |  B  0  1  0  0  0    119/ 29 |  B  0  1  0  1  1
     24/  7 |  B  0  1  0  0  0    123/ 30 |  B  0  1  3  0  0
     33/  8 |  C  0  0  1  0  0    128/ 31 |  C  0  0  1  1  1
     33/  9 |  C  0  0  1  0  0    132/ 32 |  C  0  0  4  0  0
     38/ 10 |  A  2  0  0  0  0    135/ 33 |  A  1  0  2  0  1
     45/ 11 |  D  0  0  0  1  0    140/ 34 |  B  0  1  2  0  1
     50/ 12 |  E  0  0  0  0  1    144/ 35 |  C  0  0  3  1  0
     52/ 13 |  A  1  0  1  0  0    149/ 36 |  C  0  0  3  0  1
     57/ 14 |  B  0  1  1  0  0    152/ 37 |  B  0  1  1  1  1
     57/ 15 |  A  3  0  0  0  0    156/ 38 |  B  0  1  4  0  0
     66/ 16 |  C  0  0  2  0  0    161/ 39 |  C  0  0  2  1  1
     69/ 17 |  A  1  0  0  0  1    165/ 40 |  C  0  0  5  0  0
     74/ 18 |  B  0  1  0  0  1    168/ 41 |  A  1  0  3  0  1
     78/ 19 |  C  0  0  1  1  0    173/ 42 |  B  0  1  3  0  1
     83/ 20 |  C  0  0  1  0  1    177/ 43 |  C  0  0  4  1  0
     85/ 21 |  A  1  0  2  0  0    182/ 44 |  C  0  0  4  0  1
     90/ 22 |  B  0  1  2  0  0    185/ 45 |  B  0  1  2  1  1

如表格所示, 這次我們真的用一個 m*n 的二維陣列來存, 所以使用空間為 O(mn)。 每填一列, 需要做以下工作:

  1. 檢查先前填的 n 列:
    1. 在 m-w(i) 列裡面, x(i) 用完了嗎?
    2. m-w(i) 的的價值, 加上 v(i) 是多少?
  2. 從上面挑出最佳解 (最大值)
  3. 將上面某一列拷貝下來, 其中一個數字加一

也就是每一列花 O(n) 的時間, 所以整個演算法耗時 O(mn)。

也可以多花一些時間, 少用一些空間。 先前的 m*n 二維陣列叫做 taken 好了, taken[i][j] 裡面存的是 「負重限制 i」 的最佳解裡面, x(j) 取了幾個。 現在不用 taken 陣列, 改用一個函數 taken(int i, int j) 來取代它的功能。 回想先前 「無限量供應版」 最後印出所有物品的方式, 同樣的方法可以在 O(m) 時間內算出答案。 這個函數在上面的 1.1 步需要用到; 至於第 3 步則不存在。 所以總共使用空間為 O(m) 而使用時間為 O(m^2 n)。 範例程式裡面的 ks_count 其實的是這一版。

安排一連串矩陣的乘法

線性代數 當中學到: 一連串 n 個矩陣相乘時, 只要矩陣排列的順序不變, 不論先算那個乘法, 都會得到相同的答案 (因為矩陣的乘法滿足 結合律 associativity)。 先算那個乘法, 雖然不影響答案, 卻會影響效率。 例如: (以下有關矩陣的範例以 rlab 的語法表示。 簡要地說, 以 ';' 分隔列, 以 ',' 分隔同一列上的元素) 例如若 A1=[5;2;-1;8]; A2=[-3,2]; A3=[7,0,-4;6,2,5]; 要相乘, 也就是要算:

        / 5 \  *  [ -3 2 ] *  / 7 0 -4 \
        | 2 |                 \ 6 2  5 /
        |-1 |
        \ 8 /

如果先算左邊再算右邊, 要花 8+24 個乘法; 如果先算右邊再算左邊, 則只要花 6+12 個乘法。 又如: A1=[1,2,3,4,5]; A2=[6;7;8;9;10]; A3=[11,12,13,14,15,16]; A4=[17;18;19;20;21;22] 則最快的方法是 (A1*A2)*(A3*A4) 共需要做 5+6+1 個數字的乘法; 最慢的方法是 (A1*(A2*A3))*A4 共需要做 30+30+6 個數字的乘法。 三個矩陣相乘, 只有兩種順序; 四個相乘就有五種; 如果有十幾個矩陣相乘, 有那麼多不同的運算順序, 究竟應該按照什麼樣的順序, 才可以節省時間呢? 在眾多不同的運算順序當中, 如何找出最有效率的一種 "括小括弧的方式" , 這個問題稱為 matrix-chain multiplication problem。

構想: 大不了將所有 "括小括弧的方式" 逐一列舉, 並逐一計算需要花多少個數字乘法, 再挑出最好的 ==> exhaustive search, 可以用遞迴解決! 我們想解決 n 個矩陣相乘的問題, 先假設有人可以替我們解決任何小一號或更小的問題 (給他 n-1 個矩陣, 他可以告訴我們如何相乘最有效率) 那麼我們的工作變得很簡單: 如果最後做的乘法是 A1*(A2.....An), 那麼需要花多少個數字乘法? 如果最後做的乘法是 (A1..A2)*(A3.....An), 又需要多少個數字的乘法呢? 如果最後做的乘法是 (A1..A3)*(A4.....An) 呢? ... 如果最後做的乘法是 (A1..A(n-1))*An) 呢? 每一個小問題都可請這位包工回答, 我們只需要負責整理他的答案即可。

可以看得出來, 每個小問題其實是兩個類似原題的問題。 作業: 請寫一個遞迴的程式解決此問題。

每一種括小括弧的方法, 其實正對應到一棵 expression tree。 總共有多少種? a(1)=1, a(n)=a(1)*a(n-1)+a(2)*a(n-2)...+a(n-1)*a(1) 這個數列稱為 Catalan numbers。 a(n) 大約為 Theta(4^n/n^1.5)。 想用遞迴演算法檢查每一種括小括弧的方法, 非常耗時。

仔細觀察, 發覺遞迴時, 不同的子問題, 卻經常會有共同的「孫問題」。 例如 100 個矩陣相乘時, "A31*A32..*A40 要如何乘比較有效率?" 這個孫問題, 被重複問了好多次, 像是 "A1*A2...*A40 要如何乘比較有效率?" 或是 "A31*A32...*A50 要如何乘比較有效率?" 都會用到它。 如果不要由上往下遞迴, 而是改成由下往上建「答案表」, 就快多了。 這樣要解決上層的問題時, 就不再需要一層層往下遞迴, 只要花一點點時間查現成的表格就可以了。

以下用 範例程式 做一個例子來說明。 有有 A,B,C, ... H 等八個矩陣要連乘, 其大小各為: 32x35, 35x24, 24x30, 30x36, 36x25, 25x40, 40x34, 34x35。 在程式開頭處設定: @chain = qw(32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35); 然後執行 perl matrixchain 得到以下輸出:

    B          C          D          E          F          G          H    
26880:A|B  49920:B|C  80448:B|C  91080:B|C 123080:E|F 152280:E|F 181720:B|C  A
           25200:B|C  56160:B|C  66000:B|C 101000:E|F 127960:B|C 157360:B|C  B
                      25920:C|D  45000:C|D  69000:E|F  99400:E|F 127960:G|H  C
                                 27000:D|E  57000:E|F  86500:E|F 117000:E|F  D
                                            36000:E|F  64600:E|F  95250:E|F  E
                                                       34000:F|G  63750:G|H  F
                                                                  47600:G|H  G

例如 B-G 這一格 (第 B 列, 第 G 行) 是如何算出來的呢? 考慮 「最後一個乘法究竟發生在何處?」 這個問題有五種可能性:

發生在... 左半代價 右半代價 兩半相乘代價 總計
B 與 C 之間: 0 + 99400 + 35*24*34 = 127960 <== 最小
C 與 D 之間: 25200 + 86500 + 35*30*34 = 147400
D 與 E 之間: 56160 + 64600 + 35*36*34 = 163600
E 與 F 之間: 66000 + 34000 + 35*25*34 = 129750
F 與 G 之間: 101000 + 0 + 35*40*34 = 148600

得知拆成 B 與 (C*...*G) 最佳, 共需要 127960 個乘法。

又例如 D-H 計算過程如下:

發生在... 左半代價 右半代價 兩半相乘代價 總計
A 與 A 之間: 0 + 95250 + 30*36*35 = 133050
A 與 A 之間: 27000 + 63750 + 30*25*35 = 117000 <== 最小
A 與 A 之間: 57000 + 47600 + 30*40*35 = 146600
A 與 A 之間: 86500 + 0 + 30*34*35 = 122200

得知拆成 (D*E) * (F*...*H) 最佳, 共需要 117000 個乘法。

最後, 從 A-H 那一格 (第 A 列, 第 H 行) 開始, 往回查表, 可以讀出完整的最佳 expression tree。 先從 A-H 得知最後一個乘法發生的位置在 B 與 C 之間, 再遞迴分別從 A-B 與 C-H 讀出他們的最佳乘法分別發生在 A 與 B 之間, 及 G 與 H 之間, ..., 由上而下畫出 expression tree, 進而得到最佳括括弧方式:

          /---*------------------------\
          |                            |
         /*\                /----------*-\
         | |                |             |
         A B       /--------*----\        H
                   |             |
                 /-*---\        /*\
                 |     |        | |
                 C    /*\       F G
                      | |
                      D E
        (   ) * (                         )
         A*B    (                    ) * H
                (         ) * (     )
                 C * (   )      F*G
                      D*E

很明顯, 使用空間為 O(n^2), 而表格的每一格需要花 O(n) 來填寫, 所以整個演算法耗時 O(n^3), 比直接遞迴快多了。

結論

本單元中的每個問題, 都是要 從許多排列組合當中, 找出最佳解:

  1. (LCS) X 與 Y 的許多共同子序列當中, 誰的長度最長?
  2. (Knapsack) 那麼多種不同的物件取法, 誰的價值最高?
  3. (Matrix Chain) 許多可能的 expression tree 當中, 誰的運算花費最低?

這些都是 combinatorial optimization problems。 解這類問題, 最簡單的想法就是窮舉所有可能性, 逐一比較優劣。 首先 數數看 如果要窮舉所有可能性, 把每一種排列組合列舉出來, 大約有多少組可能解需要檢查? (可高估, 不可低估) 然後就可以按照 「愚公移山與遞迴」 一篇當中的步驟, 寫出一個遞迴程式。 這個版本速度可能極慢, 但邏輯通常很簡單, 比較不容易出錯。 先求正確, 等一下再求改進效率。

撰寫遞迴程式時, 需要 「將一個大問題拆成幾個小一號的類似問題」。 筆者觀察發現: 同一個問題, 可能有很多不同的拆法, 因而會寫出不同的 遞迴程式; 但其中只有部分的拆法, 最後可以改成較有效率的動態規劃演算法。 密訣在於: 試著問一個 分類問題, 用這個問題將所有排列組合分成幾大類, 再逐類檢查看看最佳解到底落在那一類當中。 例如:

  1. (LCS, X 的尾巴與 Y 的尾巴不相同時) 誰的尾巴在最佳解裡面沒有派上用場?
  2. (無限量 integral knapsack) 最佳解裡面, 有還是沒有 x(n)?
  3. (限量 integral knapsack) 可以從最佳解裡面刪除那一件物品?
  4. (Matrix Chain) 最佳解的最後一個乘法發生在何處?

這個 "分類" 必須涵蓋所有可能性, 但不必具有唯一性 -- 每種排列組合 (每個可能解) 都必須屬於至少一個分類; 一種排列組合 (一個可能解) 重複出現在不同分類裡面, 並沒有關係。 例如限量 integral knapsack, 其實 "刪除 x(1) 的狀況" 與 "刪除 x(2) 的狀況" 可能重複解了某些小問題 (最佳解裡面可能兩者都出現 ...) 但這只浪費一點時間, 並不影響答案的正確性。 而且如果做了下一步, 把演算法改成查表式的動態規劃, 浪費的時間就更有限了。

接下來觀察遞迴過程當中, 是否有些一模一樣的孫問題, 先後被不同的子問題重複問了很多次? 若否, 恐怕就很難改用動態規劃; 若是, 那麼或許可以改設計成動態規劃演算法。 它的特色是由下而上建立表格: 預先將所有可能問到的孫問題解好, 才考慮如何解子問題。 這樣孫問題不論被問多少次, 只需要計算一次就好, 以後都只需要簡單的查表動作。 以下是筆者歸納的 「遞迴演算法 ==> 動態規劃演算法」 轉換 "公式":

  1. 將所有可能問到的小問題列出。 以 LCS 為例, 可能問到的小問題有: lcs("", ""), lcs("A", ""), lcs("", "G"), lcs("A", "G"), ...
  2. 改用一個陣列來儲存這些小問題的結果。 這個陣列有多大呢? 每個主要參數參數, 大約對應到陣列的一個維度 (dimension); 一個參數變化的範圍, 就是那個維度的大小。 例如 lcs(... , ...) 有兩個主要參數, 所以用二維陣列來儲存; 第一個參數的值, 可能有 m+1 種變化 (X 的前 0 個元素, X 的前 1 個元素, ... X 的前 m 個元素); 第二個參數的值, 可能有 n+1 種變化 (Y 的前 0 個元素, Y 的前 1 個元素, ... Y 的前 n 個元素), 所以需要一個 (m+1)*(n+1) 的陣列。
  3. 看著 (或腦海裡想像著) 這個二維陣列或三維陣列, 找出所有格子之間的相依關係。 記得這個陣列的每一格, 對應到一個題目。 解每一格的時候, 需要用到那些格? 據此決定迴圈的寫法。 例如 LCS 的兩層迴圈, 順序並不重要; 但兩個版本的 integral knapsack, 迴圈的順序就很重要, 而且正好相反。 Matrix Chain 的迴圈順序, 看程式有點複雜; 看表格就很清楚為什麼必須照這個順序。 (Q: 還有那些不同的順序也可以?)
  4. 把遞迴版的 "遞迴" 那句話, 改成 "查表"

許多常見的問題, 把程式由 exhaustive search 版改成動態規劃版, 時間複雜度往往也從 exponential time 降為 polynomial time; 當然也需要付出一點代價 -- space complexity 往往會提高一些。 不過相較於時間的改進, 空間的浪費也不過是 polynomial 而已, 相當值得的。 Q: 本篇各題如果用遞迴的方式解, 各要花多少時間?