Dynamic Programming Explained with Examples

By Khaled Md Tuhidul Hossain · 2025-12-20 · Algorithms

Dynamic programming trips people up because the name tells you nothing about what it actually is. It's not really about "programming" in the coding sense. It's a problem-solving technique where you break a problem into smaller subproblems, solve each one once, and store the results so you never redo work.

That's the whole secret. Solve small things first, remember the answers, build up to the big answer.

Interactive Visualization

Use the controls below to step through the algorithm or let it play automatically.

name: dynamic-programming
input: {"n": 8}
speed: 600

When Does DP Apply?

You need two properties:

Overlapping subproblems. The same smaller problems come up again and again. If every subproblem is unique, DP doesn't help, and you probably want divide-and-conquer instead.

Optimal substructure. The best solution to the big problem is built from the best solutions to the smaller problems. If you can't compose optimal answers from smaller optimal answers, DP won't work.

The Fibonacci Example

Fibonacci is the simplest way to see why DP matters. The recursive definition is clean: fib(n) = fib(n-1) + fib(n-2). But naive recursion is a disaster.

Look at what happens when you compute fib(5):

See all those red and orange nodes? fib(3) gets computed twice. fib(2) gets computed three times. For fib(50), this explodes into billions of redundant calls.

Two Approaches: Top-Down vs Bottom-Up

Top-Down (Memoization)

You write the recursive solution but cache results. When a subproblem comes up again, you return the cached answer instead of recomputing.

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

print(fib_memo(50))  # 12586269025, computed instantly

Bottom-Up (Tabulation)

You start from the smallest subproblems and fill a table going upward. No recursion needed.

def fib_tab(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]

print(fib_tab(50))  # 12586269025

You can even optimize space since you only need the last two values:

def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

Both approaches give you O(n) time instead of the exponential blowup from naive recursion.

The 0/1 Knapsack Problem

Now let's tackle something more practical. You've got a knapsack with a weight limit, and items with different weights and values. You want to maximize value without exceeding the weight limit. Each item is all-or-nothing, you can't take half of it.

Example: Capacity = 7

Building the DP Table

We build a 2D table where dp[i][w] is the maximum value using the first i items with capacity w.

For each cell, we ask: is it better to skip this item or take it?

• Skip: dp[i][w] = dp[i-1][w]
• Take (if it fits): dp[i][w] = dp[i-1][w - weight[i]] + value[i]

We pick whichever is larger.

Here's the table getting filled step by step:

The answer is in the bottom-right corner: 9. That's items B + C (weight 3+4=7, value 4+5=9).

Let's trace how dp[4][7] = 9 was decided. For item D (weight 5, value 7): taking it would give dp[3][2] + 7 = 1 + 7 = 8. Skipping gives dp[3][7] = 9. So we skip D and keep the 9 from the previous row.

Python Implementation

def knapsack(weights, values, capacity):
    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):
            # Always have the option to skip
            dp[i][w] = dp[i - 1][w]

            # Take item if it fits and improves value
            if weights[i - 1] <= w:
                take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take)

    # Backtrack to find which items were selected
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected.append(i - 1)
            w -= weights[i - 1]

    return dp[n][capacity], selected


weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7

max_value, items = knapsack(weights, values, capacity)
print(f"Max value: {max_value}")
print(f"Selected items: {items}")

Output:

Max value: 9
Selected items: [2, 1]  # Items C and B

More Classic DP Problems

Coin Change

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

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

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

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


coins = [1, 5, 10, 25]
print(coin_change(coins, 36))  # 3 (25 + 10 + 1)
print(coin_change(coins, 30))  # 2 (25 + 5)

The substructure here is simple: the best way to make amount i is one coin plus the best way to make i - coin. You try every coin and keep the minimum.

Longest Common Subsequence

Given two strings, find the length of their longest common subsequence. This shows up in diff tools, DNA sequence alignment, and version control.

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
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Reconstruct the subsequence
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            result.append(s1[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, subseq = lcs("ABCBDAB", "BDCAB")
print(f"Length: {length}, Subsequence: {subseq}")
# Length: 4, Subsequence: BCAB

Edit Distance

How many single-character operations (insert, delete, replace) to turn one string into another? This is everywhere, from spell checkers to fuzzy search.

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

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    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]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1],  # replace
                )

    return dp[m][n]


print(edit_distance("kitten", "sitting"))  # 3
print(edit_distance("sunday", "saturday")) # 3

Time and Space Complexity Summary

Most 2D DP tables can be compressed to a single row if you only need the previous row's values. It's a nice optimization when memory matters.

The DP Problem-Solving Pattern

Here's how I approach a new DP problem:

1. Find the state. What variables define a subproblem? For knapsack, it's the item index and remaining capacity.
2. Write the recurrence. How does the answer for a big state depend on smaller states?
3. Identify base cases. What are the trivial subproblems you can answer directly?
4. Decide direction. Top-down is easier to write, bottom-up is usually faster and avoids stack overflow on large inputs.
5. Optimize if needed. Can you reduce the space from 2D to 1D? Do you actually need all the states?

Wrapping Up

DP is a skill you build by doing problems. The pattern recognition gets easier with practice. Start with Fibonacci and knapsack until they feel obvious, then move to things like LCS, edit distance, and coin change.

The trick is always the same. Figure out your state, figure out your recurrence, handle the base cases, and fill in the table. Once you spot that a problem has overlapping subproblems and optimal substructure, you know DP is the right tool. The rest is just working through the details.