Dynamic Programming for Coding Interviews

Dynamic programming (DP) sounds intimidating, but the idea is simple: if you'd solve the same smaller problem many times, solve it once and remember the answer. Most DP interview problems follow the same four steps.

Dynamic programming is writing each answer down once, so the next step can reuse it instead of working it out again.

When is it DP?

Two signs:

The answer is built from answers to smaller versions of the same problem (the number of ways to reach step 10 depends on the ways to reach steps 9 and 8).
Those smaller problems repeat. A plain recursive solution would compute the same thing over and over.

Typical wording: "how many ways", "minimum / maximum cost", "longest / shortest ... such that", "is it possible to ...".

The four steps

Step through: Solving a DP problem

Step 1 of 4

Define the state

Say in words what one subproblem means, e.g. ways(i) = number of ways to reach step i. Most of the difficulty is here.

So is dynamic programming just recursion with a cache?

Top-down: recursion with memoisation

Write the recurrence as a recursive function and cache results.

python
1from functools import cache
2 
3@cache
4def ways(i):
5    if i <= 1:
6        return 1
7    return ways(i - 1) + ways(i - 2)

It's often the fastest way to a correct answer, because it reads like the recurrence. The downside is recursion depth: large inputs can overflow the call stack.

Bottom-up: filling a table

Compute states from smallest to largest in a loop, storing them in a list (or a 2D grid).

python

1def ways(n):

2    table = [1] * (n + 1)

table[i] = ways to reach step i

3    for i in range(2, n + 1):

smallest steps first

4        table[i] = table[i - 1] + table[i - 2]

the recurrence

5    return table[n]

the final answer

No recursion, and it's easy to see the time and space. Time is (number of states) × (work per state). Space is the table's size.

Filling the stairs table1 / 5

	0	1	2	3	4	5
ways	1	1

Base cases: 1 way to reach step 0, and 1 way to reach step 1.

Shrinking the memory

If each state only needs the last row or the last two values, keep just those. The stairs table above only ever looks two steps back, so two variables are enough: O(1) space instead of O(n). Interviewers like hearing this as a follow-up improvement.

Common DP shapes

Shape	State	Examples
1D sequence	best answer up to position i	Stairs, house robber, max subarray
Choice with amounts	best answer for amount a	Coin change, knapsack
Two sequences	answer for prefixes `a[:i]` and `b[:j]`	Longest common subsequence, edit distance
Grid	answer for cell (r, c)	Unique paths, minimum path sum

Common mistakes

Jumping to code before defining the state in words.
Wrong base cases, especially for "zero items" or "amount 0".
Using infinity carelessly: when "impossible" is a possible answer, check for it before returning.
Greedy shortcuts: picking the biggest coin first doesn't always give the fewest coins. DP considers every option.

Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.