What Is Dynamic Programming? Overlapping Subproblems Explained

Dynamic programming has an intimidating name for a plain idea: when a recursive solution keeps solving the same smaller problem, solve it once and reuse the answer. The name is historical and says nothing about the technique. What makes DP hard in interviews is not the caching, which is one decorator in Python, but recognising when it applies and what exactly the "smaller problem" is. This article is about that recognition.

The problem it solves

Many problems break naturally into smaller versions of themselves: the number of ways to climb n stairs depends on the ways to climb n - 1 and n - 2; the cheapest route from a city depends on the cheapest routes from its neighbours. Written as plain recursion, these solutions are short and correct, and often exponentially slow, because the recursion tree asks the same question over and over. The textbook case is Fibonacci: computing fib(25) naively makes 242,785 calls to answer only 26 distinct questions.

DP removes the repetition. The cost of the whole computation drops from "size of the recursion tree" to "number of distinct subproblems times the work per subproblem".

The intuition

Two properties must both hold.

• Overlapping subproblems. The same subproblem is reached by many paths. If every subproblem is fresh, a cache is written and never read. Merge sort splits [5, 2, 9, 1] into halves that never meet again, which is why it is divide and conquer, not DP.
• Optimal substructure. The best answer to the whole is built from best answers to the parts. Cheapest routes have it: the best route from A through B contains the best route from B. Longest simple routes do not: the longest path from a to b and the longest from b to c can share cities, so gluing them gives a route that is not simple at all.

When both hold, the solution follows a recipe:

1. State: what uniquely identifies a subproblem (an index, a city, a pair of indices, remaining capacity).
2. Recurrence: how a state's answer combines smaller states' answers.
3. Base cases: the states answered directly.
4. Order: memoize the recursion (top-down), or fill a table so every state comes after the ones it needs (bottom-up). The trade-offs are covered in memoization vs tabulation.

Greedy algorithms are the other neighbour: they also rely on optimal substructure, but commit to one choice per step instead of comparing all of them, which only works when a local choice is provably safe.

Watch it run

The animation puts the same seven-node tree to two uses. First, merge sort on [5, 2, 9, 1]: split at the midpoint, twice, until every piece is a single value. Two halves, then four singles, and every label is different. No subproblem ever repeats, so a cache would be written to and never read: 0 of 7 reused, divide and conquer, not DP. Then fib(4), the exact same branching shape, one call splitting into two smaller calls. fib(4) needs fib(3) and fib(2), and fib(3) needs fib(2) all over again. There it is: fib(2) computed twice, from scratch, including everything underneath it. fib(1) too, three times once the calls inside the repeated fib(2) are counted. At n = 4 that is mildly annoying; at n = 50 the tree has billions of nodes. Cache fib(2) the first time and the second call is a lookup, so its whole subtree never runs. Overlapping subproblems plus optimal substructure is the pair that makes a problem a DP problem, and the price is memory: every cached answer occupies space for the whole computation, time bought with space.

The code

A tracer that counts how often a recursive solver asks each distinct subproblem, run on merge sort (subproblem: a slice) and Fibonacci (subproblem: n):

from collections import Counter

def count_subproblems(solve, arg):
    """Run a recursive solver and count how often each distinct subproblem is asked."""
    seen = Counter()
    def traced(x):
        seen[x] += 1
        return solve(traced, x)
    traced(arg)
    return sum(seen.values()), len(seen), max(seen.values())   # calls, distinct, worst repeat

data = [5, 2, 9, 1]

def merge_sort(rec, span):                          # subproblem = a slice (lo, hi) of data
    lo, hi = span
    if hi - lo <= 1:
        return data[lo:hi]
    mid = (lo + hi) // 2
    left, right = rec((lo, mid)), rec((mid, hi))
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out, i = out + [left[i]], i + 1
        else:
            out, j = out + [right[j]], j + 1
    return out + left[i:] + right[j:]

def fib(rec, n):                                    # subproblem = n
    return n if n < 2 else rec(n - 1) + rec(n - 2)

print(count_subproblems(merge_sort, (0, len(data))))   # (7, 7, 1)  nothing ever repeats
print(count_subproblems(fib, 4))                       # (9, 5, 3)  fib(1) is asked three times
print(count_subproblems(fib, 25))                      # (242785, 26, 75025)

The recipe on a problem that is not Fibonacci, the cheapest route through a one-way road map, and the counterexample where optimal substructure fails:

from functools import lru_cache

roads = {"A": {"B": 2, "C": 5}, "B": {"C": 1, "D": 7}, "C": {"D": 2, "E": 9},
         "D": {"E": 3}, "E": {}}

@lru_cache(maxsize=None)
def cheapest(city):                                 # 1. state: where you stand
    if city == "E":                                 # 3. base case: already there
        return 0
    return min((cost + cheapest(nxt) for nxt, cost in roads[city].items()),
               default=float("inf"))                # 2. recurrence: best first road + best rest

print(cheapest("A"), cheapest.cache_info().currsize)   # 8 5  one answer per city, ever

# Optimal substructure can fail. Longest simple path on the square a-b-c-d-a:
square = {"a": "bd", "b": "ac", "c": "bd", "d": "ac"}

def simple_paths(graph, start, goal, path=None):
    path = path or [start]
    if start == goal:
        yield path
        return
    for nxt in graph[start]:
        if nxt not in path:
            yield from simple_paths(graph, nxt, goal, path + [nxt])

longest = lambda s, t: max(simple_paths(square, s, t), key=len)
shortest = lambda s, t: min(simple_paths(square, s, t), key=len)
print("".join(shortest("a", "b")), "+", "".join(shortest("b", "c")), "->", "".join(shortest("a", "c")))
# ab + bc -> abc   best pieces make the best whole
glued = longest("a", "b") + longest("b", "c")[1:]
print("".join(glued), len(set(glued)) == len(glued))   # adcbadc False  best pieces collide

Step 4, the order, is the lru_cache: each city is solved once, in whatever order the recursion first needs it. Checked on 500 seeded random one-way road maps against a brute force that walks every route, plus the exact call count of naive Fibonacci, 2·fib(n + 1) - 1, for n up to 25:

import random

def all_route_costs(graph, city, goal):
    """Brute force: walk every route to the goal and total its cost."""
    if city == goal:
        yield 0
    for nxt, cost in graph[city].items():
        for rest in all_route_costs(graph, nxt, goal):
            yield cost + rest

rng = random.Random(30)
ok = True
for _ in range(500):
    n = rng.randint(1, 9)                           # edges only go forward: no cycles
    graph = {i: {j: rng.randint(1, 20) for j in range(i + 1, n) if rng.random() < 0.5}
             for i in range(n)}

    @lru_cache(maxsize=None)
    def best(i):
        if i == n - 1:
            return 0
        return min((c + best(j) for j, c in graph[i].items()), default=float("inf"))

    ok &= best(0) == min(all_route_costs(graph, 0, n - 1), default=float("inf"))

a, b = 0, 1
for n in range(1, 26):                              # calls of naive fib(n) = 2 * fib(n + 1) - 1
    a, b = b, a + b
    ok &= count_subproblems(fib, n)[0] == 2 * b - 1
print(ok)                                           # True

The complexity

• DP time = distinct states × work per state. Fibonacci: n + 1 states × O(1) = O(n). Cheapest route: every city once and every road once, O(V + E).
• Naive time = size of the recursion tree: 2·fib(n + 1) - 1 calls for Fibonacci, which grows like 1.618^n.
• Space = the stored states, plus the recursion depth for the top-down version. The big-O cheat sheet lists the common DP shapes side by side.

Where it goes wrong

• A state that is too small. If the answer depends on something the state does not record, such as which cities are already used, the cache returns wrong answers. The longest simple path needs the visited set in its state, which makes the state count exponential.
• Caching without repeats. Memoizing merge sort costs memory and saves nothing.
• Mutable arguments. lru_cache needs hashable arguments; pass tuples or indices, not lists.
• Deep recursion. Top-down on a long chain can hit Python's recursion limit; fill a table bottom-up instead.

When it shows up in interviews

Constantly: climbing stairs, coin change, 0/1 knapsack, longest common subsequence and edit distance. The signals are "count the ways", "minimum or maximum", "can you reach", combined with choices at each step whose effects overlap.

How to say it in an interview

"The brute force recursion here solves the same subproblem many times, and the best answer is built from best sub-answers, so it's a dynamic programming problem. The state is the index I'm at; the recurrence takes the best over the choices from there; the base case is the end. I'll memoize it first, which makes the time the number of states times the work per state, and if recursion depth is a concern I'll turn it into a table filled in dependency order, then keep only the rows I still need."