Dynamic programming explained: how it works, code and examples

What problem dynamic programming solves

Many problems ask for the best, the cheapest or the number of ways: the fewest coins that make an amount, the longest common subsequence of two strings, the most valuable set of items that fits in a bag, the number of paths through a grid. A direct recursive solution often recomputes the same smaller cases an exponential number of times. DP removes that repetition.

The name comes from Richard Bellman, who developed the method in the 1950s. "Programming" here means planning or filling in a table, not writing code.

The idea in plain words

Naive recursive Fibonacci shows the problem. fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again, and so on: the number of calls grows exponentially. Storing each result the first time it is computed makes every later call instant.

1. Define the state: what does a subproblem look like? For example, best[a] = fewest coins that make amount a.
2. Write the recurrence: how is a state computed from smaller states? best[a] = 1 + min(best[a - c] for each coin c).
3. Set the base cases: best[0] = 0.
4. Choose the order: top-down with memoization, or bottom-up so that smaller states are always filled first.
5. Read the answer from the right state, and rebuild the actual choice if needed.

Top-down: memoization with functools

In Python, functools.cache (Python 3.9+) or functools.lru_cache adds memoization to a function with one line:

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))  # 23416728348467685

Without the decorator, fib(80) would make more than 10¹⁶ recursive calls. With it, each value from 0 to 80 is computed once.

Worked example: coin change, bottom-up

Coins 1, 3 and 4; amount 6. A greedy approach takes 4 first and needs 4 + 1 + 1 = 3 coins, but 3 + 3 uses only 2. DP finds the true minimum by filling best[a] for a = 0 to 6:

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

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

A two-dimensional example: longest common subsequence

Many DP problems on two sequences use a grid: dp[i][j] is the answer for the first i characters of one string and the first j of the other. For the longest common subsequence (LCS), if the characters match, extend the diagonal; otherwise take the better of dropping one character from either string.

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 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])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

One LCS of length 4 is BCBA. The same table structure solves edit distance, which is how text diff tools measure how different two strings are.

Time and space complexity

The general rule: time = number of states × work per state; space = number of states stored.

Knapsack's O(n × W) is pseudo-polynomial: it depends on the numeric value W, not on the input size in bits, so it is slow when W is huge.

Common mistakes and when to use DP

• Wrong state: if the recurrence needs information the state does not hold (for example, which items are already used), the answer is wrong. Add that information to the state.
• Wrong filling order: a bottom-up loop must compute every state before it is read.
• Off-by-one in table size: a string of length n needs n + 1 rows to include the empty prefix.
• Deep recursion: a memoized recursion over 10,000 states can exceed Python's recursion limit; switch to bottom-up.
• Unhashable arguments: functools.cache needs hashable arguments, so pass tuples instead of lists.

Typical interview and real-world uses: climbing stairs, house robber, longest increasing subsequence, word break, unique paths in a grid, edit distance, knapsack, matrix chain multiplication; in practice, sequence alignment in bioinformatics, diff tools, spell checkers, speech recognition (the Viterbi algorithm) and shortest paths such as Bellman-Ford.