Dynamic Programming

What Is Dynamic Programming?

Dynamic Programming (DP) is a method for solving problems by breaking them into smaller subproblems — smaller, self-similar versions of the original question. If those subproblems overlap (meaning a naive recursive approach would solve the same subproblem multiple times), DP saves each answer the first time and reuses it later. That's the core trick: compute once, use many times.

A Brief History

Richard Bellman invented dynamic programming in the 1950s while working at the RAND Corporation on optimization problems for the US Air Force. The name was deliberately vague. Bellman later explained that his boss hated the word "research" and mathematical terms made him uncomfortable, so Bellman chose "dynamic programming" because "dynamic" sounded energetic and hard to criticize, and "programming" referred to planning and scheduling (not computer programming). The name stuck, even though it tells you nothing about the technique.

Bellman also developed the Bellman equation, which is the foundation of modern reinforcement learning. Every time a self-driving car or game-playing AI makes a decision, it's solving a form of dynamic programming.

Two Requirements

Two things must be true for DP to apply:

• Optimal substructure: The best solution to the full problem can be built from the best solutions to its parts. Think shortest paths — the shortest path from A to C through B uses the shortest path from A to B and from B to C. If this property doesn't hold (e.g., the longest simple path problem), DP won't give correct results.
• Overlapping subproblems: The same subproblem gets solved multiple times in a naive approach. Fibonacci is the classic: computing fib(5) recursively computes fib(3) twice and fib(2) three times. If subproblems don't overlap (like in merge sort — each subarray is unique), you don't need DP; plain divide-and-conquer suffices.

DP vs Greedy vs Divide-and-Conquer

These three paradigms are often confused:

• Greedy: Make the locally best choice at each step. No backtracking. Fast, but only correct for problems with the greedy choice property.
• Divide-and-conquer: Split into non-overlapping subproblems, solve independently, combine. Merge sort, binary search. No caching needed because subproblems don't repeat.
• Dynamic programming: Split into overlapping subproblems, cache results. Explores all options (like exhaustive search) but avoids redundant work through memoization. Slower than greedy but handles more problems correctly.

Where DP Shows Up

• Resource allocation: Knapsack problems — fitting items into a budget, weight limit, or schedule
• Text comparison: Longest Common Subsequence (LCS) powers diff tools, DNA sequence alignment, and plagiarism detection
• Pathfinding: Counting paths in a grid, minimum cost paths, Floyd-Warshall all-pairs shortest paths
• String processing: Edit distance (what powers autocorrect), regular expression matching, word break
• Finance: Stock trading with cooldowns, coin change, optimal game strategy
• Machine learning: The Viterbi algorithm (used in speech recognition and NLP) is DP. Hidden Markov Models use DP. Reinforcement learning's value iteration is DP.

How It Works

There are two approaches, and they produce the same results. Pick whichever fits the problem better (or whichever makes more sense to you — there's no wrong choice).

Top-Down (Memoization)

Write the recursive solution first, then add a cache. When a function is called with arguments you've seen before, return the stored result instead of recomputing. The word memoization (not "memorization") comes from "memo" — you're leaving a note to yourself.

• Start from the full problem and break it down
• Only solve subproblems that actually get needed (lazy evaluation)
• Uses recursion + a hash map or array as cache
• Risk: deep recursion can blow the call stack on large inputs
• Advantage: easier to write — just add @lru_cache to your recursive function

Bottom-Up (Tabulation)

Build a table starting from the smallest subproblems and work your way up. Each cell depends only on cells you've already filled in — no recursion at all.

• Start from the base cases and iterate forward
• Solves every subproblem (even ones you might not need)
• Uses iteration + an array/matrix — no recursion overhead, no stack overflow risk
• Often faster in practice due to no function call overhead and better cache locality
• Advantage: easier to optimize space (rolling arrays, keeping only the last row)

Choosing Top-Down vs Bottom-Up

Start top-down to get the recurrence right, then convert to bottom-up if you need space optimization or to avoid stack overflow. In interviews, top-down is faster to write. In production, bottom-up is more predictable. Both are correct.

Common DP Categories

• 1D DP: Single array. Fibonacci, climbing stairs, house robber. State depends on 1-2 previous values. Often space-optimizable to O(1).
• 2D DP: Matrix/grid. LCS, edit distance, grid paths. State depends on row and column. Often space-optimizable to O(n) using rolling rows.
• Knapsack: Choose items with weights and values to maximize profit within a limit. Two variants: 0/1 knapsack (take it or leave it — each item used at most once) vs unbounded knapsack (unlimited copies of each item, like coin change).
• Interval DP: Merge or split ranges. Matrix chain multiplication, burst balloons, palindrome partitioning. The state is usually (start, end) of a range.
• State machine DP: Track which "state" you're in. Stock trading with cooldowns (states: holding, not holding, cooling down). The transition depends on your current state and the decision you make.
• Bitmask DP: Use a bitmask to represent which elements are "used." The Traveling Salesman Problem uses dp[mask][city] where mask is a bit vector of visited cities. Useful when n is small (≤ 20) because there are 2ⁿ possible masks.

Interactive Visualization

Watch how DP fills a table cell by cell. Switch between Fibonacci (1D) and Coin Change (tabulation) to see how dependencies flow. Hover over cells to see which earlier cells they depend on.

Common Mistakes

Complexity Analysis

DP doesn't have a single Big-O — it depends on the problem. But there's a formula that works every time:

Time = (number of subproblems) × (work per subproblem)

Space = (number of subproblems stored)

For Fibonacci: n subproblems × O(1) work each = O(n). For LCS: m×n subproblems × O(1) work each = O(mn). For LIS with binary search: n subproblems × O(log n) work each = O(n log n).

Implementation

Fibonacci — Top-Down vs Bottom-Up vs Space-Optimized

# Top-down: recursive with memoization
def fib_memo(n, cache={}):
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    # Store result so we never recompute fib(n)
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]

# Bottom-up: iterative tabulation
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        # Each cell only depends on the two before it
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Space-optimized: we only need 2 variables
# Since dp[i] depends only on dp[i-1] and dp[i-2],
# there's no reason to keep the entire array
def fib_opt(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1
      

Coin Change (Minimum Coins)

def coin_change(coins, amount):
    """Find the fewest coins needed to make 'amount'.
    dp[i] = minimum coins to make amount i.
    Transition: dp[i] = min(dp[i - coin] + 1) for each coin.
    This is unbounded knapsack — each coin can be used unlimited times."""
    
    # Initialize to infinity (no solution yet)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins to make amount 0

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

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

0/1 Knapsack

def knapsack(weights, values, capacity):
    """Maximize total value without exceeding capacity.
    Each item can be taken at most once (0/1 = take or leave).
    dp[i][w] = max value using first i items with capacity w."""
    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):
            # Option 1: skip item i (don't take it)
            dp[i][w] = dp[i - 1][w]
            # Option 2: take item i (if it fits)
            if weights[i - 1] <= w:
                take = values[i - 1] + dp[i - 1][w - weights[i - 1]]
                dp[i][w] = max(dp[i][w], take)

    return dp[n][capacity]

# Space-optimized: 1D array, iterate capacity RIGHT to LEFT
# (to avoid using the same item twice in one row)
def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        # MUST go right to left — otherwise dp[w - weights[i]]
        # would use the current item's row, not the previous one
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    return dp[capacity]
      

Longest Common Subsequence

def lcs(text1, text2):
    """Find the length of the longest common subsequence.
    A subsequence is a sequence derived by deleting some (or no)
    elements without changing the order of remaining elements.
    Example: lcs("abcde", "ace") = 3 (the subsequence "ace")."""
    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]:
                # Characters match — extend the LCS by 1
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # No match — take the better of skipping either character
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]
      

Edit Distance (Levenshtein Distance)

def edit_distance(word1, word2):
    """Minimum operations (insert, delete, replace) to transform
    word1 into word2. Powers autocorrect, spell checkers, and
    DNA sequence alignment.
    dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]."""
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: transforming to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # Delete all characters from word1
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters of word2

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # Characters match — no cost
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # Delete from word1
                    dp[i][j - 1],      # Insert into word1
                    dp[i - 1][j - 1]   # Replace in word1
                )

    return dp[m][n]
      

Longest Increasing Subsequence (O(n log n))

import bisect

def lis(nums):
    """Find the length of the longest strictly increasing subsequence.
    The O(n²) DP approach checks all previous elements for each position.
    This O(n log n) approach uses patience sorting (like sorting cards).
    
    tails[i] = smallest possible ending element of all increasing
    subsequences of length i+1 found so far."""
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            # num is bigger than everything — extend longest subsequence
            tails.append(num)
        else:
            # Replace to keep tails as small as possible
            # This doesn't change the LIS length but keeps options open
            # for future elements
            tails[pos] = num
    return len(tails)
      

Real-World Example: Autocorrect (Edit Distance)

When you type "recieve" and your phone suggests "receive," it's using edit distance. The algorithm computes the minimum number of character insertions, deletions, and replacements to transform one word into another, then suggests dictionary words with the smallest edit distance.

def autocorrect(typed_word, dictionary, max_distance=2):
    """Suggest corrections for a misspelled word.
    Returns dictionary words within max_distance edits,
    sorted by edit distance (closest first).
    
    This is a simplified version of what your phone keyboard does.
    Real autocorrect also considers key proximity, word frequency,
    and context (what you typed before)."""

    def edit_dist(w1, w2):
        m, n = len(w1), len(w2)
        # Quick length check — if lengths differ by more than
        # max_distance, we can skip the full DP computation
        if abs(m - n) > max_distance:
            return max_distance + 1

        dp = list(range(n + 1))  # Space-optimized: single row
        for i in range(1, m + 1):
            prev = dp[0]
            dp[0] = i
            for j in range(1, n + 1):
                temp = dp[j]
                if w1[i-1] == w2[j-1]:
                    dp[j] = prev
                else:
                    dp[j] = 1 + min(prev, dp[j], dp[j-1])
                prev = temp
        return dp[n]

    # Score every dictionary word
    suggestions = []
    for word in dictionary:
        dist = edit_dist(typed_word.lower(), word.lower())
        if dist <= max_distance:
            suggestions.append((dist, word))

    suggestions.sort()  # Sort by distance, then alphabetically
    return [word for dist, word in suggestions]

# Example
dictionary = ["receive", "recipe", "receipt", "recite", "deceive",
              "relieve", "believe", "retrieve", "achieve"]
print(autocorrect("recieve", dictionary))
# ['receive']  — distance 1 (swap i and e)

print(autocorrect("receve", dictionary))
# ['receive', 'recite']  — both distance 2
      

Edit distance is one of the most practically useful DP algorithms. Beyond autocorrect, it powers DNA sequence alignment (bioinformatics uses a weighted variant called the Needleman-Wunsch algorithm), plagiarism detection, and the Unix diff tool (which uses a variant of LCS).

Interview Patterns

The DP Recipe

1. Define the state: What does dp[i] (or dp[i][j]) represent? Write it in a comment. Be precise — "dp[i] is the answer for i" is too vague.
2. Find the transition: How does dp[i] relate to smaller subproblems? This is the recurrence relation. It's the hardest step.
3. Set base cases: What's dp[0]? dp[1]? Handle the smallest inputs where the recurrence doesn't apply.
4. Figure out the order: Which direction do you iterate? Make sure all dependencies are filled before you need them.
5. Extract the answer: Is it dp[n]? max(dp)? dp[m][n]? Know where the final answer lives in your table.

Recognizing DP Subcategories

• "Take or skip" → Knapsack pattern. House robber, subset sum, partition problems.
• "Two strings" → LCS/edit distance pattern. Build a 2D table indexed by positions in each string.
• "Count paths in a grid" → Each cell = sum of cells you can arrive from. Usually dp[i][j] = dp[i-1][j] + dp[i][j-1].
• "Best time to buy/sell" → State machine DP. Track states like "holding stock" vs "not holding" vs "in cooldown."
• "Partition into subsets" → Reduce to subset sum, which is a knapsack variant. dp[target] = can we reach this sum?

Practice Problems

Sorted by difficulty. Start with the first two to build intuition, then tackle the harder ones.