Remember what you’ve already solved
Imagine someone asks you “what’s 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1?” You count: 8. Then they add ”+ 1” and ask again. You don’t recount from the start; you answer 9 immediately, because you remember 8.
Dynamic programming is that habit, in code:
- Break the problem into smaller versions of itself (“the number of ways to climb 10 stairs depends on the ways to climb 9 and 8”).
- Notice the overlap: the same smaller problems are needed again and again.
- Store each answer the first time you compute it, and reuse it after that.
You can do it top-down (recursion plus a cache, called memoizationMemoizationCaching the results of a function call so the same inputs are never computed twice.Open in glossary →) or bottom-up (fill a table from the smallest problems upward, called tabulation).
DP applies when a problem has optimal substructure (an optimal answer is built from optimal answers to subproblems) and overlapping subproblems (the same subproblems recur). The work is modeling: choose a state that captures exactly what the future depends on, a transition relating it to smaller states, base cases, and an evaluation order. Complexity is then (number of states) × (work per transition).
Senior-level questions go further: 2-D states (sequences, grids), the loop order that distinguishes 0/1 from unbounded knapsack, space optimization with rolling arrays, reconstructing the actual solution, and the trade-offs between recursion with memoization (only reachable states, but stack depth) and iteration. All in the Detailed version.
// Exponential: fib(n - 2) is computed again inside fib(n - 1), and so on.
func slowFib(_ n: Int) -> Int {
n < 2 ? n : slowFib(n - 1) + slowFib(n - 2)
}
// Top-down: the same recursion, with a cache.
func fib(_ n: Int, _ memo: inout [Int: Int]) -> Int {
if n < 2 { return n }
if let known = memo[n] { return known }
let result = fib(n - 1, &memo) + fib(n - 2, &memo)
memo[n] = result
return result
}
// Bottom-up: from the smallest answers up, keeping only what's needed.
func fastFib(_ n: Int) -> Int {
var (a, b) = (0, 1) // fib(0), fib(1)
for _ in 0..<n { (a, b) = (b, a + b) }
return a
}// Exponential: fib(n - 2) is computed again inside fib(n - 1), and so on.
fun slowFib(n: Int): Long = if (n < 2) n.toLong() else slowFib(n - 1) + slowFib(n - 2)
// Top-down: the same recursion, with a cache.
fun fib(n: Int, memo: MutableMap<Int, Long> = HashMap()): Long {
if (n < 2) return n.toLong()
memo[n]?.let { return it }
return (fib(n - 1, memo) + fib(n - 2, memo)).also { memo[n] = it }
}
// Bottom-up: from the smallest answers up, keeping only what's needed.
fun fastFib(n: Int): Long {
var a = 0L
var b = 1L // fib(0), fib(1)
repeat(n) { val next = a + b; a = b; b = next }
return a
}// Exponential: fib(n - 2) is computed again inside fib(n - 1), and so on.
static long slowFib(int n) {
return n < 2 ? n : slowFib(n - 1) + slowFib(n - 2);
}
// Top-down: the same recursion, with a cache.
static long fib(int n, Map<Integer, Long> memo) {
if (n < 2) return n;
Long known = memo.get(n);
if (known != null) return known;
long result = fib(n - 1, memo) + fib(n - 2, memo);
memo.put(n, result);
return result;
}
// Bottom-up: from the smallest answers up, keeping only what's needed.
static long fastFib(int n) {
long a = 0, b = 1; // fib(0), fib(1)
for (int i = 0; i < n; i++) { long next = a + b; a = b; b = next; }
return a;
}// Exponential: fib(n - 2) is computed again inside fib(n - 1), and so on.
function slowFib(n: number): number {
return n < 2 ? n : slowFib(n - 1) + slowFib(n - 2);
}
// Top-down: the same recursion, with a cache.
function fib(n: number, memo = new Map<number, number>()): number {
if (n < 2) return n;
const known = memo.get(n);
if (known !== undefined) return known; // not "if (known)": 0 is a valid answer
const result = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, result);
return result;
}
// Bottom-up: from the smallest answers up, keeping only what's needed.
function fastFib(n: number): number {
let [a, b] = [0, 1]; // fib(0), fib(1)
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a; // exact up to fib(78); use bigint beyond
}All three compute the same numbers. The slow one takes O(2ⁿ) time because it recomputes the same values over and over; the two DP versions compute each value once, O(n). The bottom-up version also notices that it only ever needs the last two answers, so it uses O(1) memory.
A cache that forgets
Tap the line with the bug.
func ways(_ n: Int) -> Int {
var memo: [Int: Int] = [:]
if n <= 2 { return n }
if let known = memo[n] { return known }
let result = ways(n - 1) + ways(n - 2)
memo[n] = result
return result
}fun ways(n: Int): Int {
val memo = HashMap<Int, Int>()
if (n <= 2) return n
memo[n]?.let { return it }
val result = ways(n - 1) + ways(n - 2)
memo[n] = result
return result
}int ways(int n) {
Map<Integer, Integer> memo = new HashMap<>();
if (n <= 2) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = ways(n - 1) + ways(n - 2);
memo.put(n, result);
return result;
}function ways(n: number): number {
const memo = new Map<number, number>();
if (n <= 2) return n;
const known = memo.get(n);
if (known !== undefined) return known;
const result = ways(n - 1) + ways(n - 2);
memo.set(n, result);
return result;
}Hint: How many different memo dictionaries exist while computing ways(40)?
The cache is created inside the function, so every call gets a brand-new, empty one. No call ever finds an answer stored by another call, and the function is exactly as exponential as before: ways(45) takes seconds instead of microseconds. It looks like memoization in code review, and the answers are correct, so tests pass.
The memo must be shared by all calls of one computation: pass it in, or keep it outside the recursive function.
func ways(_ n: Int) -> Int {
var memo: [Int: Int] = [:]
func solve(_ k: Int) -> Int {
if k <= 2 { return k }
if let known = memo[k] { return known }
let result = solve(k - 1) + solve(k - 2)
memo[k] = result
return result
}
return solve(n)
}fun ways(n: Int, memo: MutableMap<Int, Int> = HashMap()): Int {
if (n <= 2) return n
memo[n]?.let { return it }
return (ways(n - 1, memo) + ways(n - 2, memo)).also { memo[n] = it }
}int ways(int n) { return ways(n, new HashMap<>()); }
int ways(int n, Map<Integer, Integer> memo) {
if (n <= 2) return n;
Integer known = memo.get(n);
if (known != null) return known;
int result = ways(n - 1, memo) + ways(n - 2, memo);
memo.put(n, result);
return result;
}function ways(n: number, memo = new Map<number, number>()): number { // created once, then passed down
if (n <= 2) return n;
const known = memo.get(n);
if (known !== undefined) return known;
const result = ways(n - 1, memo) + ways(n - 2, memo);
memo.set(n, result);
return result;
}(And don’t fix it by making the memo a global: a cache that outlives the computation leaks memory and leaks state between unrelated calls, such as different inputs in a test run.)
How bad is “without memory”?
Predict the output
How many times is fib called to compute fib(5) with the naive recursion?
var calls = 0
func fib(_ n: Int) -> Int {
calls += 1
return n < 2 ? n : fib(n - 1) + fib(n - 2)
}
_ = fib(5)
print(calls)var calls = 0
fun fib(n: Int): Int {
calls++
return if (n < 2) n else fib(n - 1) + fib(n - 2)
}
fib(5)
println(calls)static int calls = 0;
static int fib(int n) {
calls++;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
fib(5);
System.out.println(calls);let calls = 0;
function fib(n: number): number {
calls++;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
fib(5);
console.log(calls);Each call makes two more until n < 2: fib(5) calls fib(4) and fib(3), fib(4) calls fib(3) and fib(2), and so on. Counting calls: c(0) = c(1) = 1 and c(n) = 1 + c(n − 1) + c(n − 2), so c(2) = 3, c(3) = 5, c(4) = 9, c(5) = 15. The count grows like the Fibonacci numbers themselves, about 1.6ⁿ: c(30) is about 2.7 million, c(50) over 40 billion. With memoization, fib(n) makes about 2n calls.
Top-down or bottom-up?
Memoized recursion is often easier to write correctly (it mirrors the recurrence) and only visits reachable states, which matters for sparse state spaces. Its costs: recursion depth (a top-down solution over 10⁵ states can overflow the stack), hash-map overhead, and harder space optimization. Bottom-up loops are faster in practice and make the memory layout explicit. A common workflow: write the recurrence top-down, then convert it to a table once the order is clear.
- Top-down memoization mirrors the recurrence and visits only reachable states, but costs recursion depth and hashing; bottom-up tables are faster and make memory explicit. Write it top-down, convert once the order is clear.
- The memo must be shared by one computation’s calls: not recreated per call, not a global that outlives it.
Check this part
What makes a problem suitable for dynamic programming?
What is memoization?
A memo dictionary is created inside the recursive function. What happens?
A top-down solution has 10⁵ states in a chain. What can go wrong that a bottom-up loop avoids?