Dynamic Programming
Topic 6 of 7, with 3 concept checks. Recognizing overlapping subproblems and choosing top-down vs bottom-up
Store the answer to the smallest reusable state
Reusable subproblems
Define a state that contains everything the future needs, write its transition from smaller states, and establish base cases before choosing memoization or tabulation.
Core lesson 01
DP applies when a problem has optimal substructure AND overlapping subproblems - the second property is what memoization/tabulation actually exploits.
Optimal substructure alone just means recursion is possible. What makes DP specifically valuable is overlapping subproblems: without caching, naive recursion re-solves the exact same subproblem exponentially many times (naive Fibonacci recomputes fib(2) thousands of times for fib(30)). Caching each subproblem's answer the first time turns exponential blowup into linear or polynomial time.
# naive recursive fibonacci -- O(2^n), massive recomputation
def fib_naive(n):
if n <= 1: return n
return fib_naive(n-1) + fib_naive(n-2)
# memoized -- O(n), each subproblem computed exactly once
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)What to remember
What two properties make a problem a good fit for dynamic programming?
Common footguns
- Applying DP/memoization to a problem whose subproblems DON'T actually overlap - adds caching overhead with zero benefit.
Core lesson 02
Top-down (memoization) writes the recursion naturally and caches results as computed. Bottom-up (tabulation) builds a table starting from the smallest subproblems, iterating up to the final answer - avoiding recursion/call-stack overhead entirely.
Top-down is usually easier to write correctly first, since it mirrors the recursive definition of the problem directly - you just add a cache. Bottom-up requires figuring out the right iteration order (so whenever you compute table[i], everything it depends on is already filled in), which takes more upfront thought but avoids Python's recursion limit and function-call overhead, and sometimes enables further space optimization.
def climb_stairs_top_down(n, memo={}):
if n <= 2: return n
if n in memo: return memo[n]
memo[n] = climb_stairs_top_down(n-1, memo) + climb_stairs_top_down(n-2, memo)
return memo[n]
def climb_stairs_bottom_up(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]What to remember
What's the difference between top-down (memoization) and bottom-up (tabulation) DP?
Common footguns
- Using a mutable default argument as a memo cache (def f(n, memo={})) across UNRELATED calls - since the default is created once, stale cached values from a previous, different problem instance can leak in.
Core lesson 03
The DP state is the minimal set of variables fully describing 'where you are' such that future decisions only depend on that state, not the specific path taken to reach it - each independently-varying piece becomes a dimension.
For a 1D problem like climbing stairs, the state is just 'which step am I on' - one dimension. For knapsack-style problems, you typically need both 'which items have I considered' and 'how much capacity remains' - two dimensions, because remaining capacity can differ for the same item index depending on earlier choices. A debugging technique: if two different paths to the 'same' state would lead to different future decisions, your state definition is missing a dimension.
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for cap in range(capacity + 1):
dp[i][cap] = dp[i-1][cap] # skip item i-1
if weights[i-1] <= cap:
dp[i][cap] = max(dp[i][cap], dp[i-1][cap - weights[i-1]] + values[i-1])
return dp[n][capacity]What to remember
How do you decide what the DP state (the dimensions of your table) should be?
Common footguns
- Under-specifying the state (missing a dimension the future decisions actually depend on) - leads to a DP that looks plausible but silently gives wrong answers on certain inputs.
Python lab
Browser Python lab
Runtime · idle
Python loads on your first run. Your code stays in this browser.
Best practices
- Look for optimal substructure AND overlapping subproblems before reaching for DP - the second is what actually justifies caching.
- Start with a correct top-down recursive solution, THEN add memoization, THEN convert to bottom-up if needed for performance.
- Never use a mutable default argument as a memo cache across logically distinct problem calls.
- Write out the recurrence relation in plain English/math before writing any code.
Apply the concept in Interview practice
Climbing StairseasyLeetCode #70 · O(n) time, O(1) space
ways(n) = ways(n-1) + ways(n-2); build iteratively with two variables (canonical intro DP).
Open problemHouse RobbermediumLeetCode #198 · O(n) time, O(1) space
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) -- at each house, either skip it or rob it using the best from two houses back.
Open problemLongest Increasing SubsequencemediumLeetCode #300 · O(n log n) with binary search
dp[i] = length of the LIS ending at i, checking all j < i with nums[j] < nums[i]; O(n^2), or O(n log n) with patience sorting.
Open problemCoin ChangemediumLeetCode #322 · O(amount·coins) time
dp[amount] = minimum coins to make that amount, built bottom-up from dp[0] = 0, trying every coin at each amount.
Open problemLongest Common SubsequencemediumLeetCode #1143 · O(n·m) time
2D dp[i][j] = LCS length of the first i and j characters; match extends the diagonal, mismatch takes the best of skipping a character from either string.
Open problemWord BreakmediumLeetCode #139 · O(n^2) time
dp[i] = True if s[:i] can be segmented into dictionary words, checking every split point j < i where dp[j] is True and s[j:i] is in the dictionary.
Open problemConcept checks
What two properties make a problem a good fit for dynamic programming?
Hint
One is about a problem breaking into smaller versions of itself; the other is about repetition.
Optimal substructure, and overlapping subproblems.
Answer
DP applies when a problem has optimal substructure AND overlapping subproblems - the second property is what memoization/tabulation actually exploits.
Optimal substructure alone just means recursion is possible. What makes DP specifically valuable is overlapping subproblems: without caching, naive recursion re-solves the exact same subproblem exponentially many times (naive Fibonacci recomputes fib(2) thousands of times for fib(30)). Caching each subproblem's answer the first time turns exponential blowup into linear or polynomial time.
# naive recursive fibonacci -- O(2^n), massive recomputation
def fib_naive(n):
if n <= 1: return n
return fib_naive(n-1) + fib_naive(n-2)
# memoized -- O(n), each subproblem computed exactly once
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)Watch out
- Applying DP/memoization to a problem whose subproblems DON'T actually overlap - adds caching overhead with zero benefit.
What's the difference between top-down (memoization) and bottom-up (tabulation) DP?
Hint
One starts from the original problem and recurses down; the other builds up from the smallest subproblems first.
Both compute the same subproblems - the difference is direction and whether you use the call stack.
Answer
Top-down (memoization) writes the recursion naturally and caches results as computed. Bottom-up (tabulation) builds a table starting from the smallest subproblems, iterating up to the final answer - avoiding recursion/call-stack overhead entirely.
Top-down is usually easier to write correctly first, since it mirrors the recursive definition of the problem directly - you just add a cache. Bottom-up requires figuring out the right iteration order (so whenever you compute table[i], everything it depends on is already filled in), which takes more upfront thought but avoids Python's recursion limit and function-call overhead, and sometimes enables further space optimization.
def climb_stairs_top_down(n, memo={}):
if n <= 2: return n
if n in memo: return memo[n]
memo[n] = climb_stairs_top_down(n-1, memo) + climb_stairs_top_down(n-2, memo)
return memo[n]
def climb_stairs_bottom_up(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Watch out
- Using a mutable default argument as a memo cache (def f(n, memo={})) across UNRELATED calls - since the default is created once, stale cached values from a previous, different problem instance can leak in.
How do you decide what the DP state (the dimensions of your table) should be?
Hint
Ask: what information do I need to know to make the next decision?
Every piece of that information that can vary independently becomes a dimension.
Answer
The DP state is the minimal set of variables fully describing 'where you are' such that future decisions only depend on that state, not the specific path taken to reach it - each independently-varying piece becomes a dimension.
For a 1D problem like climbing stairs, the state is just 'which step am I on' - one dimension. For knapsack-style problems, you typically need both 'which items have I considered' and 'how much capacity remains' - two dimensions, because remaining capacity can differ for the same item index depending on earlier choices. A debugging technique: if two different paths to the 'same' state would lead to different future decisions, your state definition is missing a dimension.
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for cap in range(capacity + 1):
dp[i][cap] = dp[i-1][cap] # skip item i-1
if weights[i-1] <= cap:
dp[i][cap] = max(dp[i][cap], dp[i-1][cap - weights[i-1]] + values[i-1])
return dp[n][capacity]Watch out
- Under-specifying the state (missing a dimension the future decisions actually depend on) - leads to a DP that looks plausible but silently gives wrong answers on certain inputs.