動態規劃 II：自底向上的表格

從快取到表格

記憶化是惰性地填快取，按遞迴恰好遊走的任何順序。自底向上的 DP 反其道而行：它有意地去填一個[[dsa-array|陣列]]（那張*表*），從基準情形出發，一路向上挺進到答案。表的規則正是同一個遞推式——對費波那契是 `dp[i] = dp[i-1] + dp[i-2]`——但現在由*你*來決定填表順序，使得當你計算 `dp[i]` 時，它需要的兩個格子裡都已經裝著答案了。

i :   0   1   2   3   4   5   6
dp:  [0] [1] [ ] [ ] [ ] [ ] [ ]    <- start: base cases filled

           fill left to right, each = sum of its two left neighbors:
dp:  [0] [1] [1] [2] [3] [5] [8]
            ^---^
            dp[2] = dp[1] + dp[0] = 1 + 0 = 1
                            ... up to dp[6] = dp[5] + dp[4] = 5 + 3 = 8

費波那契的 DP 表。嚴格從左到右地填，保證每個格子的兩個依賴都已經算好。

#include <vector>

long long fib(int n) {
    if (n <= 1) return n;
    std::vector<long long> dp(n + 1);
    dp[0] = 0; dp[1] = 1;                 // base cases
    for (int i = 2; i <= n; i++)          // fill in dependency order
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

自底向上的費波那契：沒有遞迴，沒有呼叫堆疊，只有一個在表上的迴圈。仍是 O(n) 時間、O(n) 空間。

兩個經典：爬樓梯與硬幣兌換

爬樓梯：你每次能上 1 級或 2 級——到達第 `n` 級有多少種不同走法？要落在第 `i` 級上，你的上一步要麼來自 `i-1`、要麼來自 `i-2`，於是 `ways[i] = ways[i-1] + ways[i-2]`。這就是戴了頂帽子的費波那契。重點是：一旦你問*「上一個決定是什麼，它把我留在了什麼狀態？」*，許多 DP 的[[recurrence-relation|遞迴關係]]就長得很像了。

硬幣兌換——正是貪婪做錯的那道題。給定硬幣與目標金額，求*最少*的硬幣數。設 `dp[a]` = 湊出金額 `a` 所需的最少硬幣數。要湊 `a`，就試每一種硬幣 `c`：若用它，你還欠 `a-c`，那要花 `dp[a-c]`。於是 `dp[a] = 1 + 各硬幣中 dp[a-c] 的最小值`。從 `0` 一路建表到目標，而且不像貪婪，這一種永遠正確。

#include <vector>
#include <climits>

int coinChange(std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;                              // 0 coins make amount 0
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a && dp[a - c] != INT_MAX)
                dp[a] = std::min(dp[a], 1 + dp[a - c]);
    return dp[amount] == INT_MAX ? -1 : dp[amount];   // -1 = impossible
}

O(金額 × 硬幣種數)。對硬幣 {1,3,4}、金額 6：dp[6] 正確地變為 2（兩個 3）——修好了上一篇導讀裡貪婪的那個錯。

一張二維表：0-1 背包，輕輕地

有些問題需要一張二維表。在 0-1 背包裡，每件物品有重量和價值，你有一份重量預算，你想要最多的價值——每件物品至多拿一次。狀態是兩個數：*我已經考慮過哪些物品*（`i`），以及*還剩多少容量*（`w`）。於是 `dp[i][w]` 是一張網格。對每件物品你做一個決定——跳過它，或拿上它——並保留更好的那個結果。

          capacity w ->  0   1   2   3   4   5
          (no items)    [0] [0] [0] [0] [0] [0]
 item 1 (wt 2, val 3)   [0] [0] [3] [3] [3] [3]
 item 2 (wt 3, val 4)   [0] [0] [3] [4] [4] [7]
 item 3 (wt 4, val 5)   [0] [0] [3] [4] [5] [7]

 dp[i][w] = max( dp[i-1][w],                  // skip item i
                 val[i] + dp[i-1][w - wt[i]] ) // take item i (if it fits)
 Answer (bottom-right) = 7.

每一行加入一件物品；每個格子問「跳過還是拿？」。一個格子只讀它上面那一行——所以自上而下、從左到右地填是安全的。

壓縮表格：空間優化

這是自底向上 DP 的一個可愛的額外好處。再看看費波那契：`dp[i]` 只讀 `dp[i-1]` 和 `dp[i-2]`，它從不往更早回望。那何必留著整個陣列？兩個變數就夠了。表從 O(n) 空間縮成 O(1)。

long long fib(int n) {
    if (n <= 1) return n;
    long long prev2 = 0, prev1 = 1, cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = prev1 + prev2;   // only the last two values matter
        prev2 = prev1;
        prev1 = cur;
    }
    return cur;               // O(n) time, now O(1) space
}

因為每個費波那契值只依賴前兩個，我們只保留兩個滾動的變數，而不是整張表。

同樣的把戲也能救背包網格：既然第 `i` 行只讀第 `i-1` 行，你就可以只保留一行一維陣列、原地更新它（容量從高到低地迭代，免得覆蓋掉一個你還要用的值）。這就是為什麼人們常常*偏愛*自底向上：它讓依賴結構變得可見，而正是這份可見，讓你能壓縮記憶體、並避開深遞迴的堆疊溢位。