Dynamic Programming

Remember answers to subproblems you've already solved. The two-step recipe — recurrence first, table second — that turns 2^n into n^2.

advancedPractice Full theoryPrereq:Recursion Fundamentals

Start practice Read the theory See all problems

What you'll learn

Identify the two signals of DP: optimal substructure and overlapping subproblems
Define the DP state and write the recurrence relation
Convert a recurrence to top-down memoisation and bottom-up tabulation
Recognise the classic DP shapes (1-D, 2-D, knapsack, interval)
Compress 2-D tables to 1-D to save space
Distinguish DP (count/optimise overlapping subproblems) from backtracking (enumerate)

When to reach for this

Signals (use it)

"Maximum / minimum / longest / number of ways" over choices
The brute-force recursion re-solves the same subproblems (overlap)
Optimal answer is built from optimal answers to subproblems
Sequences/strings: subsequences, edit distance, partitions
"Can you do it with these constraints" feasibility over a budget (knapsack)

Anti-signals (don't)

A greedy local choice provably gives the optimum → greedy, no table needed
You must list every solution, not count/optimise → backtracking
Subproblems don't overlap → plain divide-and-conquer

Theory & deep dive

Dynamic programming is recursion plus memory. When a problem can be broken into subproblems that overlap (the same subproblem is solved again and again), DP stores each subproblem's answer the first time and reuses it, collapsing exponential recursion into polynomial time. That's the entire idea — everything else is bookkeeping.

DP has a reputation as the hardest topic, but it yields to a reliable recipe: (1) write the recurrence — express the answer for state n in terms of smaller states — and (2) compute it efficiently — either top-down (recursion + a cache) or bottom-up (fill a table). If you can state the recurrence in words, the code is mechanical.

This module gives you the two prerequisites that signal DP (optimal substructure + overlapping subproblems), the recurrence-first recipe, top-down vs bottom-up, the common DP shapes, and space compression.

The big idea in plain words

Dynamic programming is just doing a calculation once and scribbling the answer in the margin so you never have to redo it. If a big answer is built from smaller answers that you'll need again and again, save them instead of recomputing.

Example: ways to climb 5 stairs taking 1 or 2 steps at a time. The ways to reach step 5 equal the ways to reach step 4 plus the ways to reach step 3 (because your last move was either a 1-step or a 2-step). So you jot down each step's count as you climb - 1, 2, 3, 5, 8 - instead of recalculating the lower steps over and over. That little notebook is what turns a slow problem fast.

The two prerequisites

DP applies only when both of these hold — check them before reaching for a table.

Property	Meaning	Test
Optimal substructure	The optimal answer uses optimal answers to subproblems	Can I express f(n) from f(<n)?
Overlapping subproblems	The same subproblem recurs many times	Does naive recursion repeat work?

If only optimal substructure holds (no overlap), it's plain divide-and-conquer (like merge sort). If subproblems overlap, memoising those repeats is what gives the speed-up.

Tip

Quick test for overlap: draw the recursion tree for a small input. If the same call (e.g. fib(3)) appears in multiple places, you have overlapping subproblems — memoise them.

The recurrence-first recipe

Don't start coding a table. Start with four questions, in order:

1
What is the state? The minimal info that identifies a subproblem (e.g. dp[i] = best answer ending at index i, or dp[i][j] = answer for ranges/two sequences).
2
What is the recurrence? How does the state depend on smaller states? This is the hard, creative step.
3
What are the base cases? The smallest states you can answer directly.
4
What order fills the table? So every state's dependencies are computed first.

Write the recurrence in plain English first: 'the most money I can rob from houses 0..i is the max of (skip house i → dp[i-1]) and (rob house i → dp[i-2] + value[i])'. The code writes itself from there.

Top-down vs bottom-up

The same recurrence, two implementations.

	Top-down (memo)	Bottom-up (table)
Style	recursion + cache	iterative loops
Writes	only reachable states	all states
Stack risk	yes (deep recursion)	none
Space-optimise	harder	easy (roll the array)

Start top-down (it follows the recurrence directly), then convert to bottom-up if you need to avoid stack depth or compress space.

Java· Coin Change — bottom-up (min coins)

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);   // 'infinity'
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

The classic DP shapes

Most interview DP is one of a handful of recognisable shapes. Match the prompt to the shape and the state falls out.

Shape	State	Examples
1-D linear	dp[i] from dp[i-1], dp[i-2]	Climbing Stairs, House Robber, Max Subarray
2-D grid	dp[i][j] from neighbours	Unique Paths, Min Path Sum
Two sequences	dp[i][j] over two strings	LCS, Edit Distance
Knapsack	dp[i][capacity]	0/1 Knapsack, Partition Equal Subset, Coin Change
Interval	dp[i][j] over a range	Matrix Chain, Burst Balloons

Recognising the shape gives you the state dimensions immediately, which is usually the part people get stuck on.

Space compression

If dp[i] depends only on dp[i-1] (and maybe dp[i-2]), you don't need the whole array — just a couple of rolling variables, dropping O(n) space to O(1). Likewise, a 2-D table where row i depends only on row i-1 compresses to two rows (or one, iterating carefully) for O(min(n,m)) space. Interviewers love this optimisation; mention it even if you code the full table first.

Note

Always get a correct full-table solution working first, THEN compress. Compressing prematurely is a common source of subtle off-by-one and overwrite bugs.

How to talk about this in the interview

“Lead with the two signals: "The brute-force recursion re-solves the same subproblems, and the optimum is built from sub-optima — that's dynamic programming." Then state the recurrence in words before coding: "Let dp[i] be the max I can rob from the first i houses; then dp[i] = max(dp[i-1], dp[i-2] + value[i])." Code it top-down with a cache, give O(states × work-per-state) complexity, and offer the space-compressed version as a follow-up to show depth.”

Common mistakes

–Jumping to a table before writing the recurrence — define the state and transition first
–Wrong or missing base cases (dp[0], empty string/array)
–Filling the table in an order where a state's dependencies aren't ready yet
–Confusing DP (optimise/count overlapping subproblems) with backtracking (enumerate all)
–Compressing space before the full solution is correct, introducing overwrite bugs
–Off-by-one between 'first i items' (1-indexed dp) and 0-indexed arrays

Complexity summary

DP time is (number of states) × (work per state). 1-D problems are typically O(n); two-sequence and grid problems O(n·m); knapsack O(n·capacity). Space equals the table size, often reducible by one dimension via rolling-array compression.

Practice problems

44 total