Dynamic Programming

Use when: Overlapping subproblems, optimal substructure - “how many ways”, “min/max cost”, “can we reach”.

Complexity: Varies - typically O(N) to O(N^2) or O(N*M)

1D DP - Linear

# Example: climb stairs / coin change
def dp_1d(n):
    dp = [0] * (n + 1)
    dp[0] = 1  # base case
 
    for i in range(1, n + 1):
        for choice in choices:
            if i - choice >= 0:
                dp[i] += dp[i - choice]  # or min/max
 
    return dp[n]

2D DP - Grid

# Example: unique paths, min path sum
def dp_grid(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
 
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            from_top  = dp[r-1][c] if r > 0 else float('inf')
            from_left = dp[r][c-1] if c > 0 else float('inf')
            dp[r][c] = grid[r][c] + min(from_top, from_left)
 
    return dp[rows-1][cols-1]

2D DP - Two Sequences

# Example: LCS, edit distance
def dp_two_seq(s1, s2):
    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]

Knapsack (0/1)

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]  # skip item
            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]

Signals in a Problem

• “How many ways to…”
• “Minimum/maximum cost to…”
• “Can you reach / partition / form…”
• Choices at each step with overlapping subproblems