Dynamic programming (DP) solves problems that can be broken into smaller, overlapping subproblems. Instead of recomputing the same subproblem many times, you solve each one once and store its answer, either top-down with a cache (memoisation) or bottom-up by filling a table (tabulation). The key steps are defining the state, writing the recurrence, setting base cases, and choosing an order of computation.
Why does dynamic programming matter?
Many problems have a natural recursive solution that is far too slow because it solves the same subproblems over and over. DP turns exponential-time recursions into polynomial-time algorithms by remembering answers. It appears everywhere: shortest paths, text diffing (what git diff does), spell checking with edit distance, resource allocation, bioinformatics sequence alignment, and even parts of how speech recognition and some reinforcement learning work. It is also one of the most feared interview topics, mainly because people try to memorise solutions instead of learning a method.
What two properties make a problem suitable for DP?
- Overlapping subproblems: the same smaller problems recur many times in a naive recursion.
- Optimal substructure: the best answer to the whole problem can be built from the best answers to its subproblems.
If subproblems don't overlap (as in merge sort), plain divide and conquer is enough. If optimal substructure fails, DP won't give correct answers.
What does the classic Fibonacci example show?
The naive recursion fib(n) = fib(n−1) + fib(n−2) recomputes the same values repeatedly: fib(5) computes fib(3) twice and fib(2) three times, and the number of calls grows exponentially.
Counted for fib(0) = 0, fib(1) = 1: naive calls follow C(n) = C(n−1) + C(n−2) + 1; memoised calls are 2n − 1.
Store each fib(k) the first time it's computed and the work becomes linear. That single idea, remember instead of recompute, is the whole of DP.
What is a reliable five-step method?
- Define the state: what does dp[i] (or dp[i][j]) mean, in words? For example, "dp[i] = the minimum cost to reach step i".
- Write the recurrence: how does a state depend on smaller states? "dp[i] = cost[i] + min(dp[i−1], dp[i−2])".
- Set base cases: the smallest states you know directly, such as dp[0] and dp[1].
- Choose the order: compute states so every dependency is ready (usually increasing i).
- Find the answer: which state holds the final result, dp[n] or the maximum over all states?
Then optimise space if each state only needs the last few states.
Memoisation or tabulation?
| Aspect | Memoisation (top-down) | Tabulation (bottom-up) |
|---|---|---|
| How you write it | Recursive function plus a cache | Loops filling an array or table |
| Which states are computed | Only those actually needed | All states in the table |
| Risk | Recursion depth limits (Python's default is about 1,000) | Getting the loop order wrong |
| Space optimisation | Harder | Easier (keep only recent rows) |
| Best for learning | Start here: closest to your recursive idea | Convert to this once it works |
In Python, functools.lru_cache adds memoisation to a recursive function in one line.
Which classic DP patterns should you know?
| Pattern | Example problems | State idea |
|---|---|---|
| 1D linear | Climbing stairs, house robber, min-cost steps | dp[i] = best answer up to position i |
| Knapsack | 0/1 knapsack, subset sum, coin change | dp[i][w] = best using the first i items with capacity w |
| Two strings | Longest common subsequence, edit distance | dp[i][j] = answer for prefixes of length i and j |
| Grids | Unique paths, minimum path sum | dp[r][c] = answer for reaching cell (r, c) |
| Subsequences | Longest increasing subsequence | dp[i] = best ending at index i |
| Intervals | Matrix-chain multiplication, burst balloons | dp[l][r] = answer for the range l..r |
What does a worked example look like?
Coin change: with coins of ₹1, ₹2 and ₹5, what's the minimum number of coins for ₹11? State: dp[a] = minimum coins to make amount a. Recurrence: dp[a] = 1 + min(dp[a − c]) over coins c ≤ a. Base: dp[0] = 0. Order: a from 1 to 11. Filling the table gives dp[11] = 3 (5 + 5 + 1). Time is amount × number of coins, here 11 × 3 operations instead of exploring every combination. A greedy approach (always take the largest coin) happens to work for these coins, but not for every coin system, such as ₹1, ₹3 and ₹4 for ₹6, where greedy gives 4 + 1 + 1 but the optimum is 3 + 3. DP is always correct.
How do you get better at spotting DP?
- Trigger words: "minimum/maximum", "number of ways", "longest/shortest", "can you reach", combined with choices at each step.
- Start with brute-force recursion, draw the recursion tree, and look for repeated calls.
- Name the state in plain words before writing any code.
- Solve small inputs by hand and fill the table on paper.
- Group practice by pattern, not randomly, until each pattern feels familiar.
What mistakes do beginners make?
- Writing code before defining what the state means.
- Wrong base cases, especially for empty strings or amount zero.
- Filling the table in an order where dependencies aren't ready.
- Off-by-one errors between 0- and 1-indexed tables.
- Forgetting impossible states (use infinity for "can't reach").
Where does DP show up in AI and real systems?
DP isn't only an interview topic. The Viterbi algorithm, used in older speech recognition and sequence tagging, is DP over sequences. Edit distance powers spell checkers and fuzzy matching of names and addresses, useful for cleaning Indian datasets with many spelling variants. Reinforcement learning's value iteration is DP over states. Recognising the pattern helps you understand these algorithms instead of treating them as black boxes.
How do you reduce the memory a DP solution uses?
Many tables only need the previous row or the last few values. Climbing stairs and Fibonacci need just two variables instead of an array of n values. Knapsack needs only one row of size W if you iterate capacities from high to low, which avoids reusing an item twice. Longest common subsequence needs two rows instead of a full grid. Interviewers often ask for this optimisation after you've written a correct table solution, so practise converting O(n × m) space to O(m) once the logic is clear. If you also need to reconstruct the actual solution (which items, which characters), you may need to keep the full table or extra back-pointers, a trade-off worth stating out loud.
How is DP different from greedy and backtracking?
Greedy algorithms make the locally best choice at each step and never revisit it; they are fast but only correct when the problem has the greedy-choice property, as interval scheduling does. Backtracking explores choices recursively and undoes them, enumerating possibilities with pruning, which suits problems like generating permutations or solving Sudoku. DP explores all relevant choices like backtracking but reuses results of identical subproblems. A useful habit: try greedy, look for a counterexample, and if one exists, move to DP.
How should you practise?
Solve three problems from each pattern in the table, starting with memoisation and converting to tabulation, then reduce space where possible. Write the state definition as a comment above every solution. Dynamic programming, recursion and graph algorithms are part of the ten-week DSA phase in Program Zero; see the DSA course, Big O notation and our DSA preparation plan.