Dynamic Programming
Solve overlapping subproblems once and reuse the answer — the pattern behind "optimal" and "count the ways" problems
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
is recursion plus a memory: when the same subproblem would be solved over and over by plain recursion, store the answer the first time and reuse it.
The classic example — Fibonacci without memoization recomputes the same values exponentially:
python def fib_slow(n): # O(2ⁿ) — recomputes fib(2) many times over if n <= 1: return n return fib_slow(n - 1) + fib_slow(n - 2)
Add a cache (memoization = top-down DP) and it becomes O(n):
python def fib_memo(n, cache=None): if cache is None: cache = {} if n <= 1: return n if n in cache: return cache[n] # already solved — reuse it cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n]
The same idea written bottom-up (tabulation) — build the table forward, no recursion:
python def fib_tabulation(n): if n <= 1: return n table = [0, 1] for i in range(2, n + 1): table.append(table[i - 1] + table[i - 2]) return table[n]
Two questions answer almost every DP problem:
- 1. What's the state? — what minimal information defines a subproblem (e.g. "index i" for Fibonacci, "remaining capacity" for knapsack).
- 2. What's the recurrence? — how does the answer for a state relate to answers for smaller states (
fib(n) = fib(n-1) + fib(n-2)).
1D DP — climbing stairs (count the ways to reach the top, 1 or 2 steps at a time):
python def climb_stairs(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] # reach step i from i-1 (one step) or i-2 (two steps) return dp[n]
The tell: "count the number of ways," "find the minimum/maximum," or "is it possible to" combined with a brute-force recursive solution that re-solves identical subproblems — that overlap is what DP exploits. No overlap (every subproblem is distinct) means plain recursion is already optimal — DP buys nothing there.
Examples
Coin change — minimum coins to make an amount
dp[i] depends only on smaller amounts already solved — classic bottom-up DP
def coin_change(coins, amount):
INF = float('inf')
dp = [0] + [INF] * amount # dp[i] = min coins to make amount i
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1) # use this coin + best for the rest
return dp[amount] if dp[amount] != INF else -1
print(coin_change([1, 2, 5], 11)) # 3 (5 + 5 + 1)Longest common subsequence — 2D DP
2D DP — the state is a pair of indices, one per string, instead of a single index
def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)] # dp[i][j] = LCS length of a[:i], b[:j]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # characters match — extend
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # skip one character from either string
return dp[m][n]
print(lcs("abcde", "ace")) # 3 ("ace")How well did you understand this?