From a cache to a table
Memoization fills a cache lazily, in whatever order the recursion happens to wander. Bottom-up DP does the opposite: it fills an [[dsa-array|array]] (the *table*) on purpose, starting from the base cases and marching up to the answer. The rule for the table is exactly the same recurrence — for Fibonacci, `dp[i] = dp[i-1] + dp[i-2]` — but now *you* decide the filling order so that when you compute `dp[i]`, both cells it needs already hold their answers.
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#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];
}Two classics: climbing stairs and coin change
Climbing stairs: you can step up 1 or 2 stairs at a time — how many distinct ways to reach stair `n`? To land on stair `i`, your last move came either from `i-1` or `i-2`, so `ways[i] = ways[i-1] + ways[i-2]`. That's Fibonacci wearing a hat. The point: many DP [[recurrence-relation|recurrence relations]] look alike once you ask *"what was the last decision, and what state did it leave me in?"*
Coin change — the very problem greedy got wrong. Given coins and a target amount, find the *fewest* coins. Let `dp[a]` = fewest coins to make amount `a`. To make `a`, try each coin `c`: if you use it, you still owe `a-c`, which costs `dp[a-c]`. So `dp[a] = 1 + min over coins of dp[a-c]`. Build the table from `0` up to the target, and unlike greedy, this one is always correct.
#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
}A grid table: 0-1 knapsack, gently
Some problems need a 2-D table. In the 0-1 knapsack, each item has a weight and a value, you have a weight budget, and you want the most value — taking each item at most once. The state is two numbers: *which items have I considered* (`i`) and *how much capacity is left* (`w`). So `dp[i][w]` is a grid. For each item you make one decision — skip it or take it — and keep the better outcome.
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.Shrinking the table: space optimization
Here's a lovely bonus of bottom-up DP. Look again at Fibonacci: `dp[i]` only ever reads `dp[i-1]` and `dp[i-2]`. It never looks further back. So why keep the whole array? Two variables are enough. The table shrinks from O(n) space to 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
}The same trick rescues the knapsack grid: since row `i` only reads row `i-1`, you can keep a single 1-D row and update it in place (iterating capacity from high to low so you don't overwrite a value you still need). This is why people often *prefer* bottom-up: it makes the dependency structure visible, and that visibility is exactly what lets you compress memory and avoid deep-recursion stack overflows.