Dynamic Programming

Dynamic programming is applicable precisely when a problem has two structural properties simultaneously.

Optimal Substructure means the optimal solution to the problem contains the optimal solutions to its subproblems. This is not obvious — it must be proved for each problem. A classic counterexample is the longest simple path in a graph: the longest simple path from A to C does NOT necessarily pass through the longest simple path from A to B (because that path might reuse a vertex needed by the B-to-C leg). Shortest paths, by contrast, DO have optimal substructure: if the shortest path from s to t passes through v, then the sub-path from s to v must itself be the shortest path from s to v. This is why Dijkstra and Bellman-Ford work.

Overlapping Subproblems means the naive recursive algorithm solves the same subproblem many times. This distinguishes DP from divide-and-conquer. In merge sort, the subproblems are disjoint — the left half and right half never share elements, so there is no benefit to caching. In Fibonacci, computing fib(5) requires fib(4) and fib(3); computing fib(6) requires fib(5) and fib(4) — fib(4) is needed twice. The recursion tree is an exponential explosion of repeated work.

The formal test: draw the recursion tree. If any node appears more than once, you have overlapping subproblems. If the recurrence has the form OPT(problem) = combine(OPT(subproblem1), OPT(subproblem2)) where OPT is the same objective function, you likely have optimal substructure.

The payoff: when both properties hold, we can solve each subproblem exactly once and store the answer. The total work becomes proportional to the number of distinct subproblems times the work per subproblem (not counting recursive calls), which is typically polynomial.

# Naive Fibonacci — exponential O(2^n) due to overlapping subproblems
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# The recursion tree for fib(5):
#          fib(5)
#         /      \
#      fib(4)   fib(3)  <-- fib(3) computed TWICE
#      /    \    /  \
#  fib(3) fib(2) fib(2) fib(1)  <-- fib(2) computed THREE times
#  ...
# Each fib(k) is recomputed exponentially many times.

Memoization is the simplest path to DP: write the natural recursive solution, then add a cache. Before computing a subproblem, check if you have already solved it. If yes, return the stored answer. If no, compute it, store it, then return it.

The structure is always:

1. Define a memo dictionary (or array).
2. At the top of the recursive function, check if n in memo: return memo[n].
3. At the bottom, before returning, do memo[n] = result.

Why it works: We are performing the same recursion as the naive version, but each subproblem is computed at most once. The recursion tree becomes a DAG — every node that would have been repeated is instead a cache hit in O(1).

Time complexity: O(number of distinct subproblems × work per subproblem excluding recursive calls). For Fibonacci, there are O(n) distinct subproblems and O(1) work each, so the total is O(n) — a dramatic improvement over O(2^n).

Space complexity: O(n) for the call stack plus O(n) for the memo table — O(n) overall.

When to prefer memoization: When the subproblem space is sparse (not all subproblems will be reached from the top-level call), when the natural recursion is easy to express, or when the ordering of subproblems is non-obvious.

from functools import lru_cache

# Explicit memoization
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]          # cache hit — O(1)
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Python shorthand using lru_cache decorator
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(100))   # 354224848179261915075 — instantaneous

Tabulation fills in a DP table iteratively, from the smallest subproblems up to the answer. Instead of relying on the call stack, you explicitly compute subproblems in an order such that when you need subproblem X, all subproblems that X depends on are already in the table.

The design process:

1. Identify the state: what parameters uniquely describe a subproblem?
2. Identify the base cases: which subproblems have trivially known answers?
3. Write the recurrence: how does the answer for state (i) depend on answers for smaller states?
4. Determine the traversal order: typically smallest to largest, or left-to-right through an array.
5. Extract the final answer from the table.

Advantages over memoization:

• No recursion overhead, no risk of stack overflow for large inputs.
• Cache-friendly memory access patterns (iterating over an array sequentially is fast in hardware).
• Often allows space optimization (e.g., if the recurrence only looks back 2 rows, you only need to store 2 rows).

Disadvantage: You must compute ALL subproblems, even those never reached from the top-level call. For problems where only a fraction of subproblems are needed, memoization wins.

Key insight: memoization and tabulation compute the same function; they differ only in the order of evaluation and whether the call stack or an explicit loop controls that order.

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

# Space-optimized: only the last two values matter
def fib_opt(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# O(n) time, O(1) space

The 0/1 Knapsack is the canonical DP on bounded discrete choices. You have n items, each with a weight w[i] and value v[i]. You have a knapsack with capacity W. You can take each item at most once (0 or 1 — hence the name). Maximize total value without exceeding weight capacity.

Why greedy fails: Taking items by best value-to-weight ratio does not work because you cannot take fractional items. (The fractional knapsack, where you can take 0.3 of an item, IS solvable greedily — but that is a different problem.)

State definition: dp[i][w] = maximum value achievable using only items 1..i with weight capacity exactly w.

Recurrence:

• If we skip item i: dp[i][w] = dp[i-1][w]
• If we take item i (only if w[i] <= w): dp[i][w] = dp[i-1][w - w[i]] + v[i]
• dp[i][w] = max(skip, take)

Base cases: dp[0][w] = 0 for all w (no items available).

Optimal substructure proof: Suppose the optimal packing for items 1..i with capacity w includes item i. Then the remaining items must form an optimal packing for items 1..(i-1) with capacity (w - w[i]). Proof by contradiction: if there were a better packing of the remaining items, we could swap it in and improve the overall solution, contradicting optimality.

Complexity: O(n × W) time and space. This is pseudo-polynomial — the input size is O(n + log W) bits, and W can be exponentially large in log W. Knapsack is NP-hard in general, but this algorithm is efficient for small W.

Space optimization: The recurrence for row i only depends on row i-1. By iterating w from W down to w[i] (to avoid using the same item twice), we can reduce space to O(W).

def knapsack_01(values, weights, W):
    n = len(values)
    # dp[w] = max value with capacity w, considering items so far
    dp = [0] * (W + 1)

    for i in range(n):
        # Iterate BACKWARDS to prevent reusing item i
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w],                         # skip item i
                        dp[w - weights[i]] + values[i]) # take item i

    return dp[W]

# Example
values  = [60, 100, 120]
weights = [ 1,   2,   3]
W = 5
print(knapsack_01(values, weights, W))  # 280 (take items 2 and 3)

# To reconstruct the solution, keep a 2D table and trace back:
# if dp[i][w] != dp[i-1][w], item i was taken.

The Longest Common Subsequence problem asks: given two strings X and Y, find the length of their longest common subsequence. A subsequence is obtained by deleting characters (without reordering). For example, LCS("ABCBDAB", "BDCAB") = 4, achieved by "BCAB" or "BDAB".

LCS is foundational in bioinformatics (DNA sequence alignment), version control systems (diff), and plagiarism detection.

State definition: dp[i][j] = length of LCS of X[1..i] and Y[1..j].

Recurrence:

• If X[i] == Y[j]: this character belongs to the LCS. dp[i][j] = dp[i-1][j-1] + 1.
• Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). We try dropping the last character of X or the last character of Y and take the better result.

Base cases: dp[0][j] = dp[i][0] = 0 (empty string has no common subsequence with anything).

Complexity: O(mn) time and space, where m = |X| and n = |Y|. Space can be reduced to O(min(m,n)) by keeping only two rows.

Traceback: To reconstruct the actual LCS (not just its length), fill the entire table, then trace back from dp[m][n]: if X[i] == Y[j], include it and move diagonally; otherwise move in the direction of the larger neighbor.

Key insight: The 2D DP table is the central new pattern here. Many string DP problems — edit distance, palindrome subsequence, regex matching — use this same (i,j) state representing prefixes of two strings.

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    # dp[i][j] = LCS length of X[:i] and Y[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:           # characters match
                dp[i][j] = dp[i-1][j-1] + 1
            else:                           # drop one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

def lcs_reconstruct(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Traceback
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            result.append(X[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))

print(lcs_length("ABCBDAB", "BDCAB"))       # 4
print(lcs_reconstruct("ABCBDAB", "BDCAB"))  # BCAB (or BDAB)

Edit Distance asks: what is the minimum number of single-character edits (insert, delete, substitute) needed to transform string X into string Y? Levenshtein distance is the most common variant.

Applications: spell checkers, DNA mutation analysis, plagiarism detection, fuzzy search, OCR post-processing.

State definition: dp[i][j] = minimum edits to transform X[1..i] into Y[1..j].

Recurrence:

• If X[i] == Y[j]: no edit needed for this pair. dp[i][j] = dp[i-1][j-1].
• Otherwise, take the minimum of three options:
  • Substitute X[i] with Y[j]: dp[i-1][j-1] + 1
  • Delete X[i]: dp[i-1][j] + 1
  • Insert Y[j] after position i: dp[i][j-1] + 1

Base cases:

• dp[i][0] = i (delete all i characters of X to reach empty string)
• dp[0][j] = j (insert all j characters of Y from empty string)

Complexity: O(mn) time, O(mn) space, reducible to O(min(m,n)) space.

Relationship to LCS: Edit distance and LCS are deeply related. If L = LCS(X, Y), then edit_distance = (m - L) + (n - L) = m + n - 2L when only insertions and deletions (not substitutions) are allowed. Levenshtein distance with substitutions is strictly stronger.

The diagonal in the table: A diagonal move represents either a free match (X[i] == Y[j]) or a substitution cost of 1. A vertical move represents a deletion. A horizontal move represents an insertion. Visualizing this as a grid with costs is the key to understanding the recurrence.

def edit_distance(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1): dp[i][0] = i  # delete i chars
    for j in range(n + 1): dp[0][j] = j  # insert j chars

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1]          # free match
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],   # substitute
                    dp[i-1][j],     # delete X[i]
                    dp[i][j-1]      # insert Y[j]
                )
    return dp[m][n]

print(edit_distance("kitten", "sitting"))  # 3
# kitten -> sitten (substitute k->s)
# sitten -> sittin (substitute e->i)
# sittin -> sitting (insert g)

The Coin Change problem: given coin denominations coins[] and a target amount amount, find the minimum number of coins that sum to amount (you can use each denomination unlimited times).

This exemplifies the unbounded knapsack pattern: items can be reused. The greedy algorithm (always take the largest coin that fits) famously fails — with coins {1, 3, 4} and target 6, greedy gives 4+1+1=3 coins but the optimal is 3+3=2 coins.

State definition: dp[a] = minimum coins needed to make amount a.

Recurrence: For each amount a, try each coin c: dp[a] = min(dp[a - c] + 1) for all c in coins where c <= a

Base case: dp[0] = 0 (zero coins needed for amount 0). Initialize all other entries to infinity (amount is unreachable).

Traversal order: Because coins can be reused, we iterate a from 1 to amount (not backwards). When we compute dp[a], we are allowed to use dp[a - c] which was computed earlier in the same pass — this is what permits reuse.

Contrast with 0/1 Knapsack: In 0/1, we iterate the capacity backwards to prevent reuse. Here, we iterate forwards to allow reuse. This is the single most common source of bugs when transitioning between variants.

Complexity: O(amount × |coins|) time, O(amount) space.

Variant — Coin Change 2: Count the number of ways to make amount. The recurrence changes from min to a sum: dp[a] += dp[a - c]. The traversal order also changes — to count unordered combinations (not permutations), iterate coins in the outer loop and amounts in the inner loop.

import math

def coin_change(coins, amount):
    dp = [math.inf] * (amount + 1)
    dp[0] = 0  # base case

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

    return dp[amount] if dp[amount] != math.inf else -1

print(coin_change([1, 5, 6, 9], 11))  # 2  (6+5)
print(coin_change([2], 3))            # -1 (impossible)

# Coin Change 2: number of combinations
def coin_change_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make 0: use no coins

    for c in coins:              # outer loop = coins (ensures combinations)
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]

    return dp[amount]

print(coin_change_ways([1, 2, 5], 5))  # 4 (5; 2+2+1; 2+1+1+1; 1+1+1+1+1)

Knowing four canonical problems is useful; being able to recognize DP in a new problem and derive the recurrence from scratch is the real skill. Here is the systematic method:

Step 1 — Look for optimization or counting over a combinatorial space. DP almost always appears in: "minimize/maximize X subject to constraint Y", "count the number of ways to ...", "is it possible to ...". If the answer is a single number derived from a large space of choices, suspect DP.

Step 2 — Define the state. Ask: what information do I need to know at any point to make the optimal remaining decision, without caring about how I got here? This is the DP state. Common state patterns:

• Single index: dp[i] (working through one array)
• Two indices: dp[i][j] (two arrays/strings, or a 2D grid)
• Index + capacity: dp[i][w] (knapsack-style)
• Bitmask: dp[mask] (subset DP, e.g., Traveling Salesman for small n)

Step 3 — Write the recurrence by asking: what is the last decision made? For knapsack, the last decision is "include or exclude item n". For LCS, it is "do the last characters match?". The recurrence expresses the answer in terms of answers to strictly smaller subproblems.

Step 4 — Identify base cases — the smallest subproblems with trivially known answers.

Step 5 — Determine traversal order so that dependencies are always computed before they are needed.

Step 6 — Extract the answer from the table (often dp[n] or dp[m][n]).

Step 7 — Optimize space if needed (can you discard old rows?).

The "last step" heuristic: The most reliable way to derive the recurrence is to assume you know the optimal solution, look at its last step or last element, and ask what that implies about the structure of the rest of the solution.

# Template for 1D tabulation DP
# -----------------------------------------------
# 1. State: dp[i] represents "answer for subproblem i"
# 2. Recurrence: dp[i] = f(dp[j] for j < i)
# 3. Base: dp[0] = known_value
# 4. Order: i = 1, 2, ..., n
# 5. Answer: dp[n]

# Example: Maximum sum subarray (Kadane's = DP!)
def max_subarray(nums):
    # dp[i] = max sum of subarray ENDING at index i
    # dp[i] = max(nums[i], dp[i-1] + nums[i])
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # extend or start fresh
        best = max(best, cur)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

DP tables tell you the value of the optimal solution but not the solution itself. To reconstruct the actual choices (the items taken, the characters in the LCS, the edit operations), you must either:

Option A — Traceback: After filling the table, start from the answer cell and trace backwards, at each step asking "which subproblem did I come from?". This is O(n) or O(m+n) time and requires the full table in memory.

Option B — Track decisions during fill: Store a separate parent or choice table alongside dp. At each cell, record which case of the recurrence was used (e.g., 'take', 'skip', 'diagonal', 'up', 'left'). Traceback then follows the parent pointers.

Option C — Divide and conquer optimization (Hirschberg's algorithm for LCS): Reconstruct the LCS in O(mn) time but only O(min(m,n)) space by exploiting the fact that the optimal split point of the two strings can be found without storing the full table. This is an advanced technique.

Pitfall: If you apply space optimization (e.g., keeping only 2 rows of a 2D DP), you lose the ability to traceback. Always decide whether you need the solution or just its value before applying space optimizations.

Traceback is not just an implementation detail — it makes the DP complete as an algorithm. A problem that asks "does a solution exist?" needs only the value; a problem that asks "find an optimal schedule" needs traceback.

# 0/1 Knapsack with solution reconstruction (full 2D table)
def knapsack_with_traceback(values, weights, W):
    n = len(values)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]   # skip
            if weights[i-1] <= w:
                take = dp[i-1][w - weights[i-1]] + values[i-1]
                if take > dp[i][w]:
                    dp[i][w] = take

    # Traceback
    chosen = []
    w = W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:   # item i was taken
            chosen.append(i - 1)      # 0-indexed item
            w -= weights[i - 1]

    return dp[n][W], list(reversed(chosen))

values  = [60, 100, 120]
weights = [ 1,   2,   3]
W = 5
val, items = knapsack_with_traceback(values, weights, W)
print(val, items)   # 280 [1, 2]  (items at index 1 and 2)