Memoization vs Tabulation
Once you know a problem requires dynamic programming, you have two implementation styles to choose from:
- Memoization (top-down): write a recursive function, add a cache to avoid recomputing
- Tabulation (bottom-up): build a table iteratively from base cases up to the answer
Both have the same asymptotic time and space complexity for the same problem. The difference is in constants, stack depth, code style, and which states you compute.
Top-Down Memoization
Memoization wraps the natural recursive solution in a cache. You write the function exactly as you would think about the problem recursively, then add: "if I've computed this before, return the cached answer."
The call graph is a DAG — each unique subproblem is computed exactly once because of the cache, so the total work equals the number of unique subproblems times the work per subproblem.
// Coin Change — Memoization (top-down)
function coinChangeMemo(coins, amount) {
const memo = new Map();
function dp(remaining) {
if (remaining === 0) return 0; // base case: no coins needed
if (remaining < 0) return Infinity; // base case: impossible
if (memo.has(remaining)) return memo.get(remaining); // cache hit
let minCoins = Infinity;
for (const coin of coins) {
const sub = dp(remaining - coin);
if (sub !== Infinity) {
minCoins = Math.min(minCoins, sub + 1);
}
}
memo.set(remaining, minCoins);
return minCoins;
}
const result = dp(amount);
return result === Infinity ? -1 : result;
}
console.log(coinChangeMemo([1, 5, 6, 9], 11)); // 2 (5+6)
console.log(coinChangeMemo([2], 3)); // -1Bottom-Up Tabulation
Tabulation fills a table iteratively, starting from the base cases and building up to the answer. You need to figure out the dependency order — dp[i] must be computed after all the states it depends on.
For coin change, dp[i] depends on dp[i - coin] for each coin, so smaller indices must be computed first. We fill left to right.
// Coin Change — Tabulation (bottom-up)
function coinChangeTab(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // base case: 0 coins needed for amount 0
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] !== Infinity) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Full trace for coinChange([1,5,6], 11):
// dp[0] = 0
// dp[1] = dp[0]+1 = 1 (using coin 1)
// dp[2] = dp[1]+1 = 2
// dp[3] = 3, dp[4] = 4
// dp[5] = min(dp[4]+1, dp[0]+1) = min(5, 1) = 1 (using coin 5)
// dp[6] = min(dp[5]+1, dp[1]+1, dp[0]+1) = 1 (using coin 6)
// dp[7] = dp[6]+1 = 2 (coin 1 after coin 6)
// dp[10] = dp[5]+1 = 2 (5+5)
// dp[11] = min(dp[10]+1, dp[6]+1, dp[5]+1) = min(3, 2, 2) = 2
console.log(coinChangeTab([1, 5, 6], 11)); // 2 (5+6 or 6+5)Converting Between the Two Styles
For any DP problem, you can mechanically convert between the two styles. Here is the exact conversion recipe for coin change:
// Memoization → Tabulation conversion steps: // 1. Identify the state variables (here: 'remaining') // 2. Create a table sized for all possible states (dp[0..amount]) // 3. Fill base cases (dp[0] = 0) // 4. Determine dependency order (dp[i] uses dp[i-coin], so left to right) // 5. Replace the recursive call with a table lookup // 6. Replace memo.set with a table assignment // Before (memo): // const sub = dp(remaining - coin); // minCoins = Math.min(minCoins, sub + 1); // memo.set(remaining, minCoins); // After (tab): // dp[i] = Math.min(dp[i], dp[i - coin] + 1); // (the loop itself handles all states in order)
Rolling Array Space Optimization
Many DP tables only look back a fixed number of rows. When dp[i] only depends on dp[i-1] and dp[i-2], you need not store the entire array — just keep the last few values. This is called a rolling array (or sliding window DP).
For 2D DP tables (like LCS, edit distance), if dp[i][j] only depends on dp[i-1][...] you can reduce from O(m·n) to O(n) space by keeping only two rows.
// Climbing Stairs: full table → rolling two variables
function climbStairsFull(n) {
const dp = new Array(n + 1).fill(0);
dp[1] = 1; dp[2] = 2;
for (let i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
function climbStairsRolling(n) {
if (n <= 2) return n;
let a = 1, b = 2;
for (let i = 3; i <= n; i++) {
[a, b] = [b, a + b]; // roll: b becomes new a+b, old b becomes a
}
return b;
}
// 2D DP space optimization: LCS O(m·n) → O(n)
function lcs(text1, text2) {
const m = text1.length, n = text2.length;
// Full table would be dp[m+1][n+1] — O(m·n) space
// Since dp[i][j] depends only on dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
// We can use just two rows: prev and curr
let prev = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
const curr = new Array(n + 1).fill(0);
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
curr[j] = prev[j - 1] + 1;
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
prev = curr; // roll: curr becomes the new prev
}
return prev[n];
}
console.log(lcs('abcde', 'ace')); // 3When Each Style Is Preferable
Scenario | Prefer Memoization | Prefer Tabulation |
|---|---|---|
Code clarity | Natural recursive structure is clear | Iterative logic is clearer |
Not all states needed | Only computes reachable states | Must fill entire table |
Deep recursion risk | Risk stack overflow for large n | No recursion — no stack risk |
Space optimization | Harder to apply rolling array | Easy to reduce to O(row size) |
Constant factors | Function call overhead per state | Direct array access is faster |
Interview style | Easy to explain top-down thinking | Often cleaner final solution |
A More Complex Example: 0/1 Knapsack
The 0/1 knapsack has a 2D state: dp[i][w] = max value using the first i items with weight capacity w.
const items = [
{ weight: 2, value: 6 },
{ weight: 2, value: 10 },
{ weight: 3, value: 12 },
];
const capacity = 5;
// Memoization version
function knapsackMemo(items, capacity) {
const memo = new Map();
function dp(i, w) {
if (i === 0 || w === 0) return 0;
const key = i + ',' + w;
if (memo.has(key)) return memo.get(key);
let result;
if (items[i - 1].weight > w) {
result = dp(i - 1, w); // can't take item i
} else {
result = Math.max(
dp(i - 1, w), // skip item i
dp(i - 1, w - items[i - 1].weight) + items[i - 1].value // take item i
);
}
memo.set(key, result);
return result;
}
return dp(items.length, capacity);
}
// Tabulation version
function knapsackTab(items, capacity) {
const n = items.length;
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (items[i - 1].weight > w) {
dp[i][w] = dp[i - 1][w];
} else {
dp[i][w] = Math.max(
dp[i - 1][w],
dp[i - 1][w - items[i - 1].weight] + items[i - 1].value
);
}
}
}
return dp[n][capacity];
}
// Space-optimized tabulation — O(W) space instead of O(n·W)
function knapsackOptimized(items, capacity) {
const dp = new Array(capacity + 1).fill(0);
for (const { weight, value } of items) {
// Traverse RIGHT to LEFT to avoid using item twice in same row
for (let w = capacity; w >= weight; w--) {
dp[w] = Math.max(dp[w], dp[w - weight] + value);
}
}
return dp[capacity];
}
console.log(knapsackMemo(items, capacity)); // 16
console.log(knapsackTab(items, capacity)); // 16
console.log(knapsackOptimized(items, capacity)); // 16Comparison Summary
Property | Memoization | Tabulation |
|---|---|---|
Direction | Top-down (recursion) | Bottom-up (iteration) |
Cache structure | Hash map or array | Array / 2D array |
States computed | Only reachable states | All states in range |
Stack overflow risk | Yes (for large n) | No |
Space optimization | Harder | Easy (rolling array) |
Debug-friendliness | Easier (natural recursion) | Requires tracing the table |
First-principles ease | More natural | Requires knowing dependency order |