Eric Campbell 6 min read Engineering

Dynamic Programming: Complete Introduction and Examples

Dynamic programming is an algorithmic technique for solving optimization problems by breaking them into simpler subproblems and storing their solutions. The name is somewhat misleading—it's not about...

Key Insights

  • Dynamic programming solves complex problems by storing solutions to overlapping subproblems, trading memory for dramatic time savings—often reducing exponential algorithms to polynomial time.
  • Choose top-down (memoization) for intuitive recursive thinking and natural problem decomposition; choose bottom-up (tabulation) when you need space optimization or want to avoid stack overflow.
  • Recognizing DP problems comes down to two properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems (same subproblems recur multiple times).

What is Dynamic Programming?

Dynamic programming is an algorithmic technique for solving optimization problems by breaking them into simpler subproblems and storing their solutions. The name is somewhat misleading—it’s not about “programming” in the coding sense, but rather about filling in a table of values systematically.

The key insight is simple: if you’re solving the same subproblem multiple times, solve it once and cache the result. This transforms exponential-time recursive algorithms into polynomial-time solutions.

Don’t confuse DP with divide-and-conquer. Both break problems into subproblems, but divide-and-conquer (like merge sort) works with independent subproblems. DP handles overlapping subproblems—the same computation appears repeatedly in different branches of your recursion tree.

A problem is a good DP candidate when it has:

  1. Optimal substructure: The optimal solution can be constructed from optimal solutions of its subproblems.
  2. Overlapping subproblems: The same subproblems are solved multiple times.

When you see a problem asking for “minimum cost,” “maximum profit,” “number of ways,” or “is it possible”—start thinking DP.

The Two Approaches: Top-Down vs Bottom-Up

There are two ways to implement dynamic programming, and understanding both is essential.

Top-down (Memoization) starts with the original problem and recursively breaks it down. You add a cache to store computed results. This approach is intuitive because you write the natural recursive solution first, then add memoization.

Bottom-up (Tabulation) starts with the smallest subproblems and iteratively builds up to the final answer. You fill a table from base cases to the target.

Here’s Fibonacci implemented both ways:

# Top-down: Memoization
def fib_memo(n: int, cache: dict = None) -> int:
    if cache is None:
        cache = {}
    
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


# Bottom-up: Tabulation
def fib_tab(n: int) -> int:
    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]


# Space-optimized bottom-up
def fib_optimized(n: int) -> int:
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

Trade-offs to consider:

  • Top-down is easier to write—just add caching to your recursive solution
  • Top-down only computes needed subproblems; bottom-up computes all of them
  • Bottom-up avoids recursion stack overflow for large inputs
  • Bottom-up enables space optimization (you can often reduce from O(n) to O(1))

My recommendation: start with top-down to verify correctness, then convert to bottom-up if you need space optimization or have stack depth concerns.

Identifying DP Problems

Pattern recognition accelerates DP problem identification. Look for these signals:

Keywords that suggest DP:

  • “Find the minimum/maximum…”
  • “Count the number of ways…”
  • “Is it possible to…”
  • “Find the longest/shortest…”

Common problem categories:

  1. Counting problems: How many ways to reach a goal (climbing stairs, coin combinations)
  2. Optimization problems: Minimize cost or maximize value (knapsack, minimum path sum)
  3. Decision problems: Can you achieve a target? (subset sum, partition equal subset)
  4. String problems: Subsequences, edit distance, palindromes

The mental model I use: “If I knew the answer to a slightly smaller version of this problem, could I use it to solve the current one?” If yes, you’re likely looking at DP.

Classic Example: The Knapsack Problem

The 0/1 knapsack is the quintessential DP problem. You have items with weights and values, and a knapsack with limited capacity. Each item can be taken once or not at all. Maximize total value.

State definition: dp[i][w] = maximum value achievable using first i items with capacity w.

Recurrence relation: For each item, either take it or leave it:

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

Base case: dp[0][w] = 0 (no items means no value)

def knapsack(weights: list[int], values: list[int], capacity: int) -> tuple[int, list[int]]:
    n = len(weights)
    
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # Fill the table
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: Don't take item i-1
            dp[i][w] = dp[i - 1][w]
            
            # Option 2: Take item i-1 (if it fits)
            if weights[i - 1] <= w:
                take_value = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take_value)
    
    # Backtrack to find which items were selected
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        # If value changed, we took this item
        if dp[i][w] != dp[i - 1][w]:
            selected.append(i - 1)  # 0-indexed item
            w -= weights[i - 1]
    
    return dp[n][capacity], selected[::-1]


# Example usage
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

max_value, items = knapsack(weights, values, capacity)
print(f"Maximum value: {max_value}")  # Output: 10
print(f"Selected items (0-indexed): {items}")  # Output: [1, 3]

The backtracking step is crucial for real applications—knowing what to select, not just the maximum value.

String DP: Longest Common Subsequence

String problems often require 2D DP where dimensions represent positions in each string. The Longest Common Subsequence (LCS) finds the longest sequence present in both strings (not necessarily contiguous).

State: dp[i][j] = length of LCS of first i characters of string A and first j characters of string B.

Recurrence:

  • If A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1
  • Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
def lcs(a: str, b: str) -> tuple[int, str]:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # Print table for visualization
    print("    " + " ".join(f"{c:>2}" for c in " " + b))
    for i in range(m + 1):
        row_label = " " if i == 0 else a[i - 1]
        print(f"{row_label:>2} " + " ".join(f"{dp[i][j]:>2}" for j in range(n + 1)))
    
    # Reconstruct the LCS
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            result.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], "".join(reversed(result))


length, subsequence = lcs("ABCDGH", "AEDFHR")
print(f"\nLCS length: {length}, subsequence: {subsequence}")
# Output: LCS length: 3, subsequence: ADH

Edit distance (Levenshtein distance) uses the same 2D structure but tracks minimum operations instead.

Common Pitfalls and Optimization Techniques

Pitfalls I see constantly:

  1. Off-by-one errors: Mixing 0-indexed and 1-indexed thinking. Pick one convention and stick to it.
  2. Wrong base cases: The entire solution depends on correct initialization.
  3. Incorrect state transitions: Draw out small examples by hand before coding.
  4. Forgetting edge cases: Empty inputs, single elements, all same values.

Space optimization is where bottom-up shines. Notice that knapsack only uses the previous row. We can reduce from O(n×W) to O(W):

def knapsack_optimized(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # Iterate backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

The backwards iteration is critical—it ensures we don’t use the same item twice in one iteration.

Practice Problems and Next Steps

Build your DP intuition with these problems, roughly ordered by difficulty:

Beginner:

  • Climbing Stairs (1D, counting)
  • House Robber (1D, optimization)
  • Coin Change (1D, unbounded knapsack variant)

Intermediate:

  • Longest Increasing Subsequence (1D with binary search optimization)
  • Unique Paths (2D grid)
  • Partition Equal Subset Sum (0/1 knapsack variant)

Advanced:

  • Edit Distance (2D string DP)
  • Longest Palindromic Subsequence (2D)
  • Burst Balloons (interval DP)

The path to DP mastery is practice. Solve problems, struggle with them, and eventually the patterns become second nature. Start with the recursive solution, add memoization, then convert to tabulation. This progression builds both intuition and implementation skills.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.