Dynamic Programming

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems and caching the results. If you see “minimum cost”, “number of ways”, or “maximum profit” with recursive structure, think DP.

Why It Matters

DP turns exponential brute-force solutions into polynomial time. Many optimization and counting problems are only tractable with DP. It’s also the most common “hard” topic in interviews.

Two Approaches

Approach	Direction	Method
Top-down (memoization)	Start from the full problem, recurse down	Add a cache to recursion
Bottom-up (tabulation)	Start from the smallest subproblem, build up	Fill a table iteratively

The Pattern

1. Define the subproblem: what does dp[i] represent?
2. Find the recurrence: how does dp[i] relate to smaller subproblems?
3. Set base cases: what are the trivial answers?
4. Determine computation order: bottom-up or top-down?
5. Optimize space if possible (often only need last row/column)

Code Examples

Fibonacci (the hello world of DP)

# Brute force: O(2^n) — recomputes fib(3) billions of times for large n
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)
 
# Top-down with memoization: O(n)
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)
 
# Bottom-up: O(n) time, O(1) space
def fib_dp(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b
 
assert fib_dp(10) == 55

Coin Change (classic DP)

def coin_change(coins: list[int], amount: int) -> int:
    """Minimum coins to make amount. Return -1 if impossible."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins for amount 0
 
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
 
    return dp[amount] if dp[amount] != float('inf') else -1
 
assert coin_change([1, 5, 10, 25], 30) == 2  # 25 + 5
assert coin_change([2], 3) == -1              # impossible

Longest Common Subsequence

def lcs(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
    return dp[m][n]
 
assert lcs("abcde", "ace") == 3  # "ace"

Common DP Problems

Problem	Subproblem	Time
Fibonacci	dp[i] = dp[i-1] + dp[i-2]	O(n)
Coin change	dp[amount] = min coins	O(amount * coins)
Knapsack	dp[i][w] = max value with i items, capacity w	O(n * W)
LCS	dp[i][j] = longest common of s1[:i], s2[:j]	O(m * n)
Edit distance	dp[i][j] = min edits to transform s1[:i] to s2[:j]	O(m * n)

Related

• Recursion — DP builds on recursive thinking
• Big O Notation — DP reduces exponential to polynomial
• Greedy Algorithms — greedy works when DP’s full exploration isn’t needed
• Backtracking — explores all paths; DP caches repeated paths
• Hash Tables — used for memoization caches