Break a problem into overlapping subproblems and reuse their answers: the memoization → tabulation → space-optimization progression, taught on Fibonacci, coin change, knapsack, LCS and edit distance.
0 of 9 lessons checked off
Introduction
What it is
Dynamic programming solves a problem by combining answers to OVERLAPPING SUBPROBLEMS, computing each subproblem exactly once and reusing it.
It applies when a problem has two properties: overlapping subproblems (the same sub-question recurs) and optimal substructure (an optimal answer is built from optimal sub-answers).
Why it matters
DP is the technique that turns exponential recursion into polynomial time — fib from O(1.6ⁿ) to O(n), and it's the required tool for a huge class of counting/optimization problems (coin change, knapsack, edit distance, LIS).
It's the most feared interview topic precisely because it rewards a repeatable method over memorized solutions. Learn the method and every DP problem becomes 'define the state, write the transition'.
How it works
Five-step recipe: (1) define the STATE (what does dp[i] mean?), (2) write the TRANSITION (how does dp[i] depend on smaller states?), (3) set BASE CASES, (4) decide the ORDER of computation, (5) optionally OPTIMIZE space.
Top-down (memoization): write the natural recursion, cache results by argument. Bottom-up (tabulation): fill a table in dependency order with loops.
Space optimization: if dp[i] only reads dp[i−1] (and maybe dp[i−2]), you don't need the whole array — a few rolling variables suffice.
Where it's used
Diff tools and version control (edit distance / LCS), spell-check suggestions, DNA sequence alignment (bioinformatics), text justification, resource allocation, and reinforcement-learning value iteration.
Analogy: Climbing a staircase where each step's cost depends on the steps below: instead of re-deriving how you reached step 3 every time you think about step 5, you write the best cost to reach each step on the step itself. Later steps just read the numbers already written below them.
Interactive diagram
The naive call tree recomputes f(2) and f(1) repeatedly; caching collapses it to O(n) — DP in one picture.
Naive fib(5) call tree
Each call spawns two more. Identical subproblems (same argument) are recomputed again and again — that overlap is what DP removes.
1 / 17
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
Filling tables in dependency order; no recursion limit.
30 min
Defining state & transition
The five-step recipe; the two hardest and most important steps.
35 min
1-D DP: stairs, house robber, coin change
One-dimensional state; take-or-skip and min-over-choices.
40 min
Knapsack family
0/1 (each item once, reverse loop) vs unbounded (forward loop).
40 min
String DP: LCS & edit distance
2-D grids over two strings; match/skip/replace transitions.
45 min
2-D & grid DP
Paths, minimum path sum; row-rolling space optimization.
30 min
Advanced: LIS, matrix chain, bitmask (overview)
Interval DP, patience sorting for LIS, subset-state DP.
25 min
Operations
The full progression: naive → memo → tabulate → optimize
One problem, four solutions, showing exactly how DP develops from recursion to O(1) space.
fib(5) with memoization
Same recursion, but results are cached. Repeated subproblems become O(1) lookups, collapsing the tree to O(n) nodes.
1 / 11
1# 1. NAIVE recursion — O(1.618^n), recomputes everything2deffib_naive(n:int)->int:3ifn<=1:4returnn5returnfib_naive(n-1)+fib_naive(n-2)678# 2. MEMOIZATION (top-down) — O(n) time, O(n) space + recursion9deffib_memo(n:int,cache:dict[int,int]|None=None)->int:10ifcacheisNone:11cache={}12ifn<=1:13returnn14ifnnotincache:15cache[n]=fib_memo(n-1,cache)+fib_memo(n-2,cache)16returncache[n]171819# 3. TABULATION (bottom-up) — O(n) time, O(n) space, no recursion20deffib_table(n:int)->int:21ifn<=1:22returnn23dp=[0]*(n+1)24dp[1]=125foriinrange(2,n+1):26dp[i]=dp[i-1]+dp[i-2]# transition27returndp[n]282930# 4. SPACE-OPTIMIZED — O(n) time, O(1) space31deffib_optimized(n:int)->int:32prev,curr=0,133for_inrange(n):34prev,curr=curr,prev+curr# only last two states matter35returnprev
Time: O(n) for the last three; O(1.618ⁿ) naiveSpace: memo O(n), table O(n), optimized O(1)
Edge cases
Base cases n=0, n=1 must be set before the loop starts.
Space optimization is possible because dp[i] only reads dp[i−1] and dp[i−2].
Memoization needs the cache created OUTSIDE the recursion (or via a None default) to persist across calls.
Common mistakes
Mutable default cache={} shared across independent calls.
Optimizing space before the transition is correct — get it right, then shrink it.
Coin change (1-D min-over-choices)
dp[amount] = fewest coins to make it. Each coin offers a transition from a smaller amount; take the cheapest.
0
1
2
3
4
5
6
7
8
9
10
11
dp
0
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
dp[x] = fewest coins to make x
dp[0] = 0 (zero coins make amount 0); everything else starts at ∞ (unknown). Coins: [1, 2, 5].
1 / 13
1defcoin_change(coins:list[int],amount:int)->int:2"""Fewest coins to make amount, or -1. O(amount · coins)."""3INF=amount+1# sentinel > any real answer4dp=[0]+[INF]*amount# dp[0] = 0 coins5forxinrange(1,amount+1):6forcoinincoins:7ifcoin<=x:8dp[x]=min(dp[x],dp[x-coin]+1)9returndp[amount]ifdp[amount]!=INFelse-1
Time: O(amount · len(coins))Space: O(amount)
Edge cases
amount = 0 → 0 coins (the base case).
Unreachable amounts stay at INF → return −1.
This is UNBOUNDED (coins reused): the inner loop reads dp[x−coin] which may already include this coin.
Common mistakes
Greedy largest-coin-first — wrong for arbitrary denominations (see the greedy topic).
Forgetting the −1 case, returning a nonsense INF value.
Longest common subsequence (2-D string DP)
dp[i][j] = LCS length of the first i and first j characters. Characters match → extend the diagonal; else take the better of dropping one.
Longest common subsequence (2-D string DP)
1deflongest_common_subsequence(a:str,b:str)->int:2"""Length of the LCS of a and b. O(m·n) time, O(n) space (rolling)."""3prev=[0]*(len(b)+1)4foriinrange(1,len(a)+1):5curr=[0]*(len(b)+1)6forjinrange(1,len(b)+1):7ifa[i-1]==b[j-1]:8curr[j]=prev[j-1]+1# match: extend diagonal9else:10curr[j]=max(prev[j],curr[j-1])# skip one character11prev=curr12returnprev[len(b)]
Time: O(m · n)Space: O(n) with the rolling-row trick (O(m·n) for the full table)
Edge cases
Empty string → LCS 0 (the base row/column of zeros).
Reconstruction of the actual subsequence needs the full 2-D table (or backpointers), not the rolling version.
LCS ≠ longest common SUBSTRING (contiguous) — different recurrence.
Common mistakes
Off-by-one between string index (0-based) and dp index (1-based) — the −1 on characters.
Confusing subsequence with substring: substring resets to 0 on mismatch.
Complexity analysis
Operation
Best
Average
Worst
Space
Fibonacci / climbing stairs
O(n)
O(n)
O(n)
O(1) optimized
Coin change
O(amount·c)
O(amount·c)
O(amount·c)
O(amount)
0/1 knapsack
O(n·W)
O(n·W)
O(n·W)
O(W) rolled
LCS / edit distance
O(m·n)
O(m·n)
O(m·n)
O(min(m,n))
LIS (patience sorting)
O(n log n)
O(n log n)
O(n log n)
O(n)
Matrix chain multiplication
O(n³)
O(n³)
O(n³)
O(n²)
DP complexity = (number of states) × (work per transition). State it that way and you can size any DP before coding it.
Python implementation
Production-quality code with type hints, validation, and docstrings.
Edit distance (Levenshtein) — the 2-D DP interviewers love
1defedit_distance(word1:str,word2:str)->int:2"""Minimuminsert/delete/replaceoperationstoturnword1intoword2.3O(m·n)time,O(n)spacewitharollingrow."""4m,n=len(word1),len(word2)5# prev[j] = distance from word1[:0] to word2[:j] = j insertions6prev=list(range(n+1))78foriinrange(1,m+1):9curr=[i]+[0]*n# curr[0] = i deletions10forjinrange(1,n+1):11ifword1[i-1]==word2[j-1]:12curr[j]=prev[j-1]# characters match: no op13else:14curr[j]=1+min(15prev[j],# delete from word116curr[j-1],# insert into word117prev[j-1],# replace18)
What interviewers expect you to know
The recipe interviewers want to see
1. State: 'dp[i] represents ___' — say it in one sentence. If you can't, you don't have the DP yet.
2. Transition: how dp[i] is built from smaller states. This is the creative step.
3. Base cases. 4. Iteration order (so dependencies are ready). 5. Space optimization.
Start top-down (memoization) if the recursion is natural; convert to bottom-up if asked or if recursion depth is a risk.
Recognizing DP vs the alternatives
Signals: 'count the number of ways', 'minimum/maximum cost/length', 'can you reach/partition', and a recursive structure with REPEATED subproblems.
DP vs greedy: greedy commits to one choice; DP tries all and keeps the best. If greedy has a counterexample, it's DP.
DP vs backtracking: if backtracking revisits the same state via different paths, memoize it into DP.
The knapsack loop-direction trap
0/1 knapsack (each item once): iterate capacity DESCENDING, so an item isn't reused within the same row.
Unbounded knapsack (unlimited items): iterate capacity ASCENDING, so reuse is intended.
This single loop direction is the most common knapsack bug — be ready to explain WHY.
Common mistakes
Vague state definition
If you can't finish 'dp[i] means ___' in one sentence, the transition will be wrong. Nail the state before writing any loop.
Wrong base cases
dp[0] for coin change is 0 (zero coins make amount 0); for LCS the base row/column is 0; for edit distance it's the string length. Each is problem-specific — derive, don't guess.
Knapsack loop direction
0/1 needs a reverse capacity loop (use each item once); unbounded needs forward (reuse allowed). Getting this backwards silently changes which problem you solved.
Optimizing space too early
Collapse to rolling variables only AFTER the full-table transition is verified correct. Premature optimization hides transition bugs.
Subsequence vs substring
Subsequence DP takes max over skips; substring DP resets to 0 on mismatch. The recurrences differ — match the word in the prompt.
Mutable default cache
def f(n, memo={}) shares state across separate calls/test cases. Use memo=None and initialize inside.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
O(n^2 + n * k) where k is the number of valid sentences time · O(n * k) for memoized sentence lists space
Topic quiz
6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
How do I get better at defining the DP state?
Practice articulating 'dp[i] = the answer to the subproblem ending at / using the first i of ___'. For most 1-D problems the state is an index or amount; for strings it's a pair of prefixes; for knapsack it's (item, capacity). Say the sentence out loud before coding — a vague state is why DP feels impossible.
Should I write memoization or tabulation in interviews?
Lead with memoization: write the natural recursion, then add a cache — it's the least error-prone path and shows your thinking. Convert to tabulation if the interviewer asks, if recursion depth risks a stack overflow, or if you want easy space optimization. Both earn full marks when correct.
When can I space-optimize a DP?
When dp[i] depends only on a bounded window of previous states — dp[i−1], dp[i−2], or the previous row of a 2-D table. Then rolling variables or a single row replaces the full array. Do it AFTER verifying the transition; the full table is still needed when you must reconstruct the actual solution, not just its value.