Dynamic Programming

Dynamic programming (DP) is the pattern candidates fear most, yet it follows a systematic approach. Once you learn to identify DP problems and build state transitions, it becomes methodical.

When to Use DP

A problem is a DP candidate when it has:

1. Overlapping subproblems -- The same subproblem is solved multiple times
2. Optimal substructure -- The optimal solution contains optimal solutions to subproblems

Quick Test: If a recursive solution would recompute the same values, DP can help by storing those results.

Two Approaches

Approach	How It Works	Pros	Cons
Top-Down (Memoization)	Recursive + cache results	Intuitive, only solves needed subproblems	Recursion overhead, stack limit
Bottom-Up (Tabulation)	Iterative, fill table from base cases	No recursion, often more efficient	Must identify the right order

The 5-Step DP Process

Step 1: Identify it's a DP problem

Look for: "minimum cost," "maximum profit," "number of ways," "can you reach..."

Step 2: Define the state

What information do you need at each step? This becomes your DP array.

Step 3: Write the recurrence relation

How does the current state relate to previous states?

Step 4: Identify base cases

What are the smallest subproblems you can solve directly?

Step 5: Determine the iteration order

Bottom-up: which direction do you fill the table?

Essential DP Patterns

1D DP: Fibonacci / Climbing Stairs

# Climbing stairs: how many ways to reach step n?
def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

1D DP: House Robber

# House robber: max money without robbing adjacent houses
def rob(nums):
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    return prev1

2D DP: Longest Common Subsequence

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[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]

Classic: 0/1 Knapsack

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 w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]  # Don't take item i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                             dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

Classic: Coin Change

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

DP Pattern Recognition

Problem Signal	DP Category	Example
"Number of ways"	Counting DP	Climbing stairs, unique paths
"Minimum/maximum"	Optimization DP	Coin change, house robber
"Is it possible?"	Boolean DP	Word break, partition equal subset
"Longest/shortest sequence"	Sequence DP	LCS, LIS, edit distance
"Two strings"	2D DP	LCS, edit distance
"Items with weight/value"	Knapsack DP	0/1 knapsack, subset sum

Space Optimization

Many 2D DP problems only depend on the previous row, so you can reduce space from O(n*m) to O(n):

# Unique paths: O(n) space instead of O(m*n)
def unique_paths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    return dp[n-1]

Interview Tip: Start with the recursive solution, add memoization (top-down), then convert to bottom-up if needed. This shows your thought process clearly.

---

With algorithm patterns covered, let's move to system design -- a critical interview round at all levels. :::