Dynamic Programming

Dynamic programming (DP) solves complex problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results. It applies when a problem has optimal substructure (the optimal solution to the whole contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems are solved multiple times in a naive recursive approach).

Approaches

Top-Down (Memoization)

Write the natural recursive solution; cache results to avoid recomputation.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

Advantages: only computes needed subproblems; code mirrors the recurrence.

Bottom-Up (Tabulation)

Iteratively fill in a table, solving smaller subproblems first.

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

Advantages: no recursion overhead; explicit control over computation order; often easier to optimize space.

Classic Problems

0/1 Knapsack

Given $n$ items with weights $w_i$ and values $v_i$, and a knapsack capacity $W$: maximize total value without exceeding capacity. Each item can be included at most once.

Recurrence:

\[dp[i][c] = \max(dp[i-1][c], \; dp[i-1][c - w_i] + v_i) \quad \text{if } c \geq w_i\] \[dp[i][c] = dp[i-1][c] \quad \text{if } c < w_i\]

Time: $O(nW)$. Space: $O(nW)$; can reduce to $O(W)$ by using a 1D array.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for c in range(W, weights[i] - 1, -1):  # iterate right-to-left
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
    return dp[W]

Longest Common Subsequence (LCS)

Given strings $s$ and $t$: find the length of their longest common subsequence (characters need not be contiguous).

Recurrence:

\[dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } s[i] = t[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}\]

Time: $O(mn)$. Space: $O(mn)$; can reduce to $O(\min(m,n))$.

Longest Increasing Subsequence (LIS)

Find the length of the longest strictly increasing subsequence of an array.

$O(n^2)$ DP:

def lis_n2(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

$O(n \log n)$ using patience sorting:

import bisect

def lis_nlogn(arr):
    tails = []
    for x in arr:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

Edit Distance (Levenshtein Distance)

Minimum number of insertions, deletions, and substitutions to transform string $s$ into string $t$.

Recurrence:

\[dp[i][j] = \begin{cases} j & \text{if } i = 0 \\ i & \text{if } j = 0 \\ dp[i-1][j-1] & \text{if } s[i-1] = t[j-1] \\ 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) & \text{otherwise} \end{cases}\]

Applications: spell checking, DNA sequence alignment, diff tools.

Coin Change

Given coin denominations and a target amount: find the minimum number of coins.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for c in range(1, amount + 1):
        for coin in coins:
            if coin <= c:
                dp[c] = min(dp[c], dp[c - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Time: $O(\text{amount} \times \text{num coins})$.

Matrix Chain Multiplication

Given $n$ matrices, find the optimal parenthesization to minimize scalar multiplications.

\[dp[i][j] = \min_{i \leq k < j} (dp[i][k] + dp[k+1][j] + p_i \times p_{k+1} \times p_{j+1})\]

Time: $O(n^3)$.

DP on Sequences

Palindrome subproblems: dp[i][j] = is s[i..j] a palindrome? Longest palindromic subsequence, minimum insertions to make palindrome.

DP on intervals: dp[i][j] depends on dp[i+1][j], dp[i][j-1], and dp[i+1][j-1].

DP on Trees

Tree DP: define states at each node, typically using results from children.

Diameter of a binary tree: dp[node] = longest path through the node (max of left height + right height + 2). Propagate up.

Maximum independent set on a tree: either include the node (skip all children) or exclude it (take the maximum of children’s results).

Space Optimization

Many DP problems need only the previous row/column, enabling $O(n)$ space.

Example (LCS): iterate over rows; only keep current and previous rows.

State compression: for bitmask DP, represent subsets as integers. Common in problems involving $n \leq 20$ elements.

Identifying DP Problems

• “Minimum/maximum cost/steps/length…”
• “Count the number of ways…”
• “Is it possible to…”
• The problem involves sequences, subsets, partitions, or intervals.
• Brute-force search with exponential branching.