Dynamic Programming Basics
Picture splitting a big food bill among five friends who keep re-adding the same subtotals by hand, again and again, every time someone asks "wait, how much do I owe?" That's wasted work: the subtotal for the first three people never changes, so write it down once and reuse it. Dynamic programming (DP) is that idea turned into a technique: solve small pieces of a problem once, save the answers, and build the big answer out of the pieces you already solved. It trips up more candidates than any other topic, not because the code is hard, but because finding the right "piece" to save is hard. Get that right and the code almost writes itself.
Recursion vs memoization vs tabulation
Plain recursion re-solves the same subproblem again and again whenever subproblems overlap. That repeated work is what makes a naive recursive solution slow, often exponentially slow.
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# fib_naive(5) recomputes fib_naive(3) twice, fib_naive(2) three times, etc.
# Time: O(2^n)Memoization (top-down DP) keeps the same recursive calls, but writes each answer down in a cache the first time it's computed. The next time the same question comes up, read the cache instead of recomputing.
def fib_memo(n, cache={}):
if n <= 1:
return n
if n in cache:
return cache[n]
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
# Time: O(n), Space: O(n) for cache + O(n) recursion stackTabulation (bottom-up DP) drops recursion entirely. Instead of starting at the top and working down, you start at the smallest answers and build up, filling a table step by step, the way you'd fill in a spreadsheet row by row.
def fib_tab(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Time: O(n), Space: O(n), no recursion stack risk| Recursion | Memoization | Tabulation | |
|---|---|---|---|
| Structure | Top-down, natural to write | Top-down, with a cache | Bottom-up, a loop |
| Time when subproblems overlap | Exponential | Proportional to number of states | Proportional to number of states |
| Risk of crashing on deep input | High (deep recursion) | High | None |
| Best one to write first | Yes, to find the recurrence | Add a cache once recursion is correct | Convert once base cases and the rule are locked |
| Can you shrink the memory used? | Not really | Cache grows with the state space | Often shrinks to a couple of variables |
How to use this in an interview: write the plain recursive version first, even just in your head, to nail down the rule connecting a value to smaller ones. Add a cache to show you understand why the naive version was slow. Then offer the loop version, and shrinking the memory, as the polish. Walking through that progression out loud is itself what shows an interviewer you understand DP, not just that you memorized a template.
Remember: recursion re-solves, memoization remembers while going down, tabulation builds while going up. Same answer, three different amounts of wasted work.
State definition
The "state" is the smallest set of facts that fully answers "what's the best outcome from here?" Getting this wrong is the single most common way candidates get stuck on DP.
Ask yourself: what changes between one recursive call and the next, and what do I actually need to know to answer the question at this point?
- Climbing Stairs: the state is the current step
i.dp[i]means "number of ways to reach stepi." - House Robber: the state is the current house index
i.dp[i]means "max money you can rob from houses0throughi." - Problems comparing two strings (later in this course): the state is a pair
(i, j), your position in each string.
A useful test: if two different state definitions give different answers for what should be the same subproblem, the state is incomplete. You're missing a piece of information, often a yes/no flag like "have I already used my one free skip?"
Remember: the state is the exact question you'd have to text a friend to get back the right number. If the question is incomplete, the answer will be too.
Base cases and transitions
Every DP recurrence has exactly two parts:
- Base case(s): the smallest subproblems, answered directly with no recursion needed (for example,
dp[0] = 1,dp[1] = 1). - Transition: the rule for building
dp[i]out of smaller, already-solved states (for example,dp[i] = dp[i-1] + dp[i-2]).
Get the base case wrong, and every value built on top of it is wrong too, even if the transition rule is perfect. Always check your base cases against the smallest one or two real examples by hand before you write any code.
Remember: a wrong base case poisons the whole table. Check it by hand first, on paper, before typing anything.
Climbing Stairs
LeetCode 70, DP, Basic
Intuition: To reach step n, your last move was either a 1-step from n-1 or a 2-step from n-2. So the number of ways to reach n is the sum of the ways to reach those two prior steps. This is the Fibonacci recurrence in disguise.
Approach: dp[i] = dp[i-1] + dp[i-2], with dp[0] = 1 (one way to stand at the start: do nothing) and dp[1] = 1.
def climbStairs(n: int) -> int:
if n <= 1:
return 1
prev2, prev1 = 1, 1 # dp[0], dp[1]
for i in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1Worked example: for n = 5, the ways build up as 1, 1, 2, 3, 5, 8, so dp[5] = 8.
Complexity: Time O(n), space O(1). This is a memory shrink in action: since dp[i] only needs the two previous values, there's no need to keep the whole array.
Common mistakes: getting the base case off by one; dp[0] should be 1, not 0, since there's exactly one way to be at the ground with zero steps taken (do nothing). Using plain unmemoized recursion here gives O(2^n) for no reason.
Remember: Climbing Stairs is Fibonacci with a costume on. Spot the "last move was one of two options" shape and the recurrence follows.
Min Cost Climbing Stairs
LeetCode 746, DP, Basic
Intuition: You can start from step 0 or step 1 for free, and every step you land on costs cost[i] to leave. Minimize the total cost of getting past the top. dp[i] = minimum cost to reach step i.
Approach: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Reaching step i means paying to leave whichever of the two prior steps you came from.
def minCostClimbingStairs(cost: list[int]) -> int:
n = len(cost)
prev2, prev1 = 0, 0 # dp[0] = 0, dp[1] = 0 (both are free starting points)
for i in range(2, n + 1):
prev2, prev1 = prev1, min(prev1 + cost[i - 1], prev2 + cost[i - 2])
return prev1Complexity: Time O(n), space O(1).
Common mistakes: mixing up "cost to reach step i" with "cost of step i." The cost is paid when you leave a step, not when you land on it, and that shifts the indices in the transition. Also, forgetting the top is one step past the last index, n, not len(cost) - 1.
Remember: the cost is a toll you pay leaving a step, not an entry fee. That one detail decides which index goes where in the formula.
House Robber
LeetCode 198, DP, State selection
Intuition: At each house, you either rob it (and skip the previous one, since two adjacent houses can't both be robbed) or skip it. dp[i] = the most money you can rob from the first i houses.
Approach: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Either skip house i and carry forward dp[i-1], or rob it: nums[i] plus the best result from two houses back, since the one right before it is now off-limits.
def rob(nums: list[int]) -> int:
prev2, prev1 = 0, 0 # dp[-1] = 0 (no houses), dp[0] before loop starts
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1Complexity: Time O(n), space O(1).
Common mistakes: trying to track which houses were robbed instead of just the best total. The problem only asks for the amount, so the state is simpler than it looks at first. Also, confusing this with a greedy "always take the bigger neighbor" rule, which is wrong: DP correctly looks ahead through the recurrence, greedy doesn't.
Remember: at every house you make one binary choice, rob it or skip it, and
dp[i]remembers the best answer so far either way.
House Robber II
LeetCode 213, DP, Circular array
Intuition: The houses sit in a circle, so house 0 and house n-1 are now neighbors too, and you can't rob both. Split into two cases: rob from every house except the last, or rob from every house except the first. The answer is the better of the two, each solved with plain House Robber.
Approach: Run the House Robber I logic twice, once on nums[0:n-1] and once on nums[1:n], and take the max. Handle n == 1 as its own case, since a single house has no circle conflict at all.
def rob_ii(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
def rob_linear(houses):
prev2, prev1 = 0, 0
for num in houses:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))Complexity: Time O(n) across two linear passes, space O(n) for the slices, or O(1) extra if you pass index ranges instead of slicing.
Common mistakes: forgetting the n == 1 case. Slicing nums[:-1] and nums[1:] both produce empty lists when n == 1, which silently returns 0 instead of nums[0]. Also, trying to solve the circular case directly in one pass instead of breaking it into two linear subproblems; that reduction to plain House Robber is the entire trick.
Remember: a circle is just two lines in disguise. Solve "exclude the last house" and "exclude the first house" separately and take the better one.