动态规划 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` 行，你就可以只保留一行一维数组、原地更新它（容量从高到低地迭代，免得覆盖掉一个你还要用的值）。这就是为什么人们常常*偏爱*自底向上：它让依赖结构变得可见，而正是这份可见，让你能压缩内存、并避开深递归的栈溢出。