Dynamic Programming

Dynamic programming (DP) is a technique for solving problems by breaking them into overlapping subproblems and storing results so they are computed only once. It transforms exponential brute-force into polynomial time.

The Core Idea

Consider computing the 40th Fibonacci number recursively:

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

This calls fib(38) twice, fib(37) four times, fib(36) eight times... Total calls: O(2ⁿ). For n = 40, that is over a billion calls.

The redundancy: the same subproblem (fib(38)) is solved repeatedly. DP stores results.

def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Now each value is computed once: O(n) time, O(n) space.

Two Approaches

1. Memoisation (Top-Down)

Start with the recursive solution. Add a cache. On each call, check the cache first; store results before returning.

Memoisation is top-down: you start with the original problem and recurse down to base cases, caching along the way.

2. Tabulation (Bottom-Up)

Build a table starting from the base cases, filling in answers for larger subproblems iteratively.

def fib_tab(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Tabulation is bottom-up: no recursion, no call stack overhead, often faster in practice.

Space optimisation: Fibonacci only needs the previous two values — O(1) space:

def fib_optimal(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Recognising DP Problems

DP applies when a problem has these two properties:

1. Optimal substructure: the optimal solution to the whole problem can be built from optimal solutions to subproblems.
2. Overlapping subproblems: the same subproblems are solved repeatedly in a naive recursive approach.

Common signals in problem statements:

• "Count the number of ways..."
• "Find the minimum/maximum..."
• "Is it possible to..."
• Input involves sequences, grids, or intervals

Example: 0/1 Knapsack

You have a knapsack with capacity W and n items, each with a weight and value. Maximise total value without exceeding capacity.

Brute force: try all 2ⁿ subsets — O(2ⁿ).

DP: dp[i][w] = maximum value using the first i items with capacity w.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            # Skip item i
            dp[i][w] = dp[i - 1][w]
            # Take item i (if it fits)
            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][W]

• Time: O(n × W)
• Space: O(n × W) — reducible to O(W) with a 1D table

Example: Longest Common Subsequence (LCS)

Given two strings, find the length of their longest common subsequence.

"ABCDE" and "ACE" → LCS = "ACE", length 3.

def lcs(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   # characters match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # skip one

    return dp[m][n]

• Time: O(m × n)
• Space: O(m × n)

LCS is the foundation for diff tools, spell checkers, and DNA sequence alignment.

Example: Coin Change

Given denominations and a target amount, find the minimum number of coins to reach the target.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # base case: 0 coins to make 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

• Time: O(amount × len(coins))
• Space: O(amount)

For coins = [1, 5, 10, 25] and amount = 36:

• dp[36] = dp[11] + 1 = dp[1] + 1 + 1 + 1 = 3 (25 + 10 + 1)

The DP Design Process

1. Define the state. What information does dp[i] (or dp[i][j]) represent?
2. Write the recurrence. How does dp[i] depend on previous states?
3. Identify base cases. What are the smallest subproblems with known answers?
4. Choose top-down or bottom-up. Memoisation is easier to implement from a recursive solution; tabulation avoids stack overhead.
5. Optimise space. If dp[i] only depends on dp[i-1], you only need two rows.

Common DP Patterns

Key Takeaways

• DP applies when a problem has overlapping subproblems and optimal substructure.
• Memoisation (top-down) adds caching to recursion; tabulation (bottom-up) iteratively builds from base cases.
• The three steps: define the state, write the recurrence, identify base cases.
• Space optimisation often reduces O(n²) space to O(n) by keeping only the necessary previous rows.
• Practice recognising DP by the problem statement: "minimum/maximum," "count ways," "is it possible" with sequence or grid input almost always signals DP.