loading
loading
loading
loading
Turn exponential recursion into polynomial time by caching the answer to every subproblem the first time it's solved, so it's never recomputed.
Dynamic programming (DP) applies to problems with two properties: overlapping subproblems (the same smaller input recurs many times during naive recursion) and optimal substructure (an optimal solution is built from optimal solutions to its subproblems). When both hold, caching each subproblem's answer the first time it's computed — instead of recomputing it every time it recurs — turns an exponential-time recursion into a polynomial-time one. Memoization does this top-down (recursion plus a cache); tabulation does it bottom-up (an explicit table filled in dependency order, no recursion at all). Both compute the same answers; they differ in direction and, often, in constant factors and stack usage.
Step through dynamic programming live, one move at a time — this becomes a fully interactive visualizer.
Coming soon// Naive: O(2^n) — fib(2) alone is recomputed 8 times inside fib(6)
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Memoized: O(n) — each subproblem computed exactly once
function fibMemo(n, cache = new Map()) {
if (n <= 1) return n;
if (cache.has(n)) return cache.get(n);
const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
cache.set(n, result);
return result;
}function coinChange(coins, amount) {
// dp[a] = fewest coins to make amount a; Infinity = not yet possible
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // zero coins needed to make amount 0
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}function uniquePaths(rows, cols) {
// dp[r][c] = number of routes to reach cell (r, c) moving only right/down
const dp = Array.from({ length: rows }, () => new Array(cols).fill(1));
for (let r = 1; r < rows; r++) {
for (let c = 1; c < cols; c++) {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // arrive from above or from the left
}
}
return dp[rows - 1][cols - 1];
}| Memoization | Tabulation | |
|---|---|---|
| Direction | Top-down — starts from the target, recurses | Bottom-up — starts from the base cases, loops |
| Implementation | Recursion + a cache (map or array) | Explicit loop filling a table in order |
| Computes only what's needed | Yes — only subproblems actually reached | No — fills every cell up to the target |
| Stack usage | O(depth) call stack — can overflow if deep | None — no recursion at all |
| Code shape | Mirrors the natural recursive definition | Requires figuring out a safe fill order |
| Typical speed | Slightly slower — per-call overhead | Usually faster — tight loop, no call overhead |
Optimal substructure alone doesn't justify DP — plain divide-and-conquer (like Merge Sort) has optimal substructure too, but its subproblems never overlap, so there's nothing to cache and no speedup from memoizing. Overlapping subproblems alone doesn't either — without optimal substructure, an optimal answer might require reconsidering choices already locked in by a subproblem's own optimal solution, which caching a single 'best' sub-answer would silently break. DP is exactly the intersection of both properties.
A handful of shapes cover most interview DP problems: 1D sequence DP (Fibonacci, House Robber — dp[i] depends on a few previous dp values), 2D grid DP (Grid Paths, Minimum Path Sum — dp[r][c] depends on neighbors), knapsack-family DP (0/1 Knapsack, Coin Change, Subset Sum — a capacity/target dimension plus an items dimension), and string/sequence-pair DP (Longest Common Subsequence, Edit Distance — dp[i][j] compares prefixes of two sequences). Recognizing which shape a new problem matches is most of the work of solving it.
The 0/1 Knapsack problem — given items with weights and values, maximize value without exceeding a weight capacity, each item used at most once — needs a state that captures both 'which items have been considered' and 'how much capacity remains.' dp[i][w] = the best value achievable using only the first i items with capacity w. For each item, the recurrence picks the better of two choices: skip it (dp[i-1][w]) or take it, if it fits (value[i] + dp[i-1][w - weight[i]]). The capacity dimension is what makes this genuinely harder than Coin Change's single dimension — it's tracking a resource being consumed, not just a target being reached.
Ask three questions in order. First: does a greedy (locally-best-choice) approach provably fail on this problem — can an early locally-optimal pick paint you into a corner? If yes, DP is a candidate. Second: can the problem be expressed as a recurrence over a smaller version of itself (optimal substructure)? Third: do naive recursive calls repeat the same smaller inputs (overlapping subproblems)? If both hold, define the state (what does dp[...] mean, precisely, in one sentence?), write the recurrence, identify the base cases, then decide memoization or tabulation.
Plain recursion (see the Recursion topic) is necessary but not sufficient here — the recursive *shape* is often correct on the first try (fibNaive above is a completely correct definition of Fibonacci), but without caching, the same subproblems get re-derived exponentially many times. DP doesn't change the recursive definition; it changes only whether each subproblem's answer is computed once or many times.
The cache key must capture every piece of state the subproblem's answer actually depends on — miss one dimension (e.g., memoizing knapsack on item index alone, forgetting remaining capacity) and the cache returns a stale answer computed under different conditions. When a memoized solution gives wrong answers but the un-memoized recursive version is correct, an incomplete cache key is the first thing to check.
Memoization is one of the two ways to implement DP (the other is tabulation), but DP is really the underlying idea — identify overlapping subproblems with optimal substructure and never recompute an answer twice. Recursion is the vehicle for the top-down version specifically.
Check whether greedy demonstrably fails (an early locally-best choice can block the true optimum) and whether naive recursion reveals overlapping subproblems. If recursion alone is exponential but the subproblems repeat, that repetition is the signal DP applies.
Coin Change's only changing quantity is the remaining amount — coins can be reused, so there's no need to track which coins have been 'used up.' Knapsack items are each usable once, so the state must also track which items have been considered, requiring a second dimension.
In principle yes — they compute the same subproblem graph. In practice, tabulation requires figuring out a fill order where every dependency is already computed, which is straightforward for simple dimensional recurrences but can get awkward for less regular subproblem shapes.
Share what clicked for you and see notes from other learners on this topic.
Coming soon