Dynamic Programming — Remember What You Solved

What is it? #

Dynamic programming is recursion plus memory. When a problem breaks into smaller subproblems and the same subproblems keep reappearing, you solve each one once and reuse the answer.

That is all it is. The intimidating name hides a simple idea: stop recalculating things you already know.

There are two styles. Top-down memoisation is recursion with a cache — write the natural recursive solution, then remember the results. Bottom-up tabulation fills a table from the smallest case upwards, no recursion involved.

The skill is recognising when a problem qualifies: it needs overlapping subproblems and an optimal answer built from optimal sub-answers.

Think of it like this #

Climbing a staircase where you can take one or two steps at a time, and counting the number of possible routes.

The routes to step 10 are the routes to step 9 plus the routes to step 8. If you work that out by exploring every possible sequence, you recount the same lower steps thousands of times. If you write each step's answer on a sticky note as you go, you climb once.

Simple example #

Three classic problems: counting stair-climbing routes, the coin change from the previous lesson, and finding the longest common subsequence between two strings — which is how diff tools work.

Code #

from functools import lru_cache

# 1. Top-down: natural recursion plus a cache
@lru_cache(maxsize=None)
def ways_to_climb(n):
    if n <= 2:
        return max(n, 1)
    return ways_to_climb(n - 1) + ways_to_climb(n - 2)

print(ways_to_climb(40))       # instant; without the cache it takes minutes


# 2. Bottom-up: build a table from the smallest case up
def ways_to_climb_table(n):
    if n <= 2:
        return max(n, 1)
    previous, current = 1, 2
    for _ in range(3, n + 1):
        previous, current = current, previous + current   # only two values needed
    return current

print(ways_to_climb_table(40))


# 3. Coin change: fewest coins for any denomination system
def min_coins(amount, coins):
    best = [0] + [float("inf")] * amount
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and best[value - coin] + 1 < best[value]:
                best[value] = best[value - coin] + 1
    return best[amount] if best[amount] != float("inf") else -1

print(min_coins(11, (1, 3, 5)))      # 3  -> 5 + 5 + 1


# 4. Longest common subsequence — the basis of diff tools
def lcs(a, b):
    table = [[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]:
                table[i][j] = table[i - 1][j - 1] + 1     # characters match
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    return table[len(a)][len(b)]

print(lcs("deploy", "develop"))      # 5


# 5. 0/1 knapsack — where greedy fails and DP works
def knapsack(capacity, items):
    """items: list of (value, weight), each taken at most once."""
    best = [0] * (capacity + 1)
    for value, weight in items:
        for space in range(capacity, weight - 1, -1):     # backwards: one use each
            best[space] = max(best[space], best[space - weight] + value)
    return best[capacity]

print(knapsack(10, [(60, 5), (50, 3), (70, 4), (30, 2)]))   # 150

Why caching matters: ways_to_climb(40)

without cache   about 2 billion calls    minutes
with cache      40 calls                 instant

How it works #

ways_to_climb is the plain recursive definition. Without a cache, computing 40 recalculates 39 and 38, each of which recalculates their own overlapping subtrees — exponential work. @lru_cache stores each result the first time, so each value is computed once. One decorator turns exponential into linear.

The table version does the same thing without recursion. It notices that only the previous two values are ever needed, so it keeps two variables instead of a whole array. This is a common DP refinement: reduce the table to only the rows you still need.

min_coins fills an array where index v holds the fewest coins making amount v. Each entry is built from smaller entries already solved. This is why it succeeds where greedy failed — it considers every coin at every amount rather than committing to the largest first.

lcs uses a 2D table. Each cell answers "how long is the longest common subsequence of the first i characters of a and the first j of b". Matching characters extend the diagonal answer; otherwise the best of the two neighbouring answers carries forward. This is the algorithm behind file diffs and similarity scoring.

knapsack iterates capacity backwards, which is the trick that stops an item being used twice. Iterating forwards would produce the unbounded version where repeats are allowed.

The recipe is consistent: define what each state means, write how a state depends on smaller states, decide the base cases, then either cache the recursion or fill a table.

Real-world use #

Diff and merge tools, spell checkers and DNA sequence alignment all use edit-distance and LCS algorithms. Git's diff output is this family of algorithms.

Resource allocation problems — fitting jobs into a budget, packing shipments, choosing which features fit a release — are knapsack variants.

Text prediction, route planning with constraints, and many pricing and scheduling optimisations use DP under the hood.

In everyday application code, the useful takeaway is usually smaller: when you notice a recursive function recomputing the same inputs, caching it is the fix. functools.lru_cache turns expensive recursive work into a one-line change, and the same reasoning applies to caching expensive database or API calls.

The practical warning is memory. A 2D table over two long strings can be large, which is why production implementations often keep only the rows they need.

Common mistakes #

• Forgetting the base cases, so the recursion never terminates correctly.
• Caching a function whose arguments are unhashable, or whose result depends on external state.
• Getting the loop direction wrong in knapsack, allowing items to be reused.
• Building a full 2D table when two rows would do, and running out of memory.
• Reaching for DP when the problem has no overlapping subproblems — that is just recursion or greedy.

Practice #

Solve these three: count the ways to reach the bottom-right of an m×n grid moving only right or down; find the minimum number of edits to turn one word into another; and compute the maximum sum of non-adjacent numbers in a list. Write each with memoisation first, then convert one to a bottom-up table.