algorithmsintermediate 75m read

L33 · DP I — Recognising Overlapping Subproblems

DP is recursion plus a cache. Write the recursion, add lru_cache, convert to a table — mechanically, in that order, every time.

🧩DSAPhase 2 · Dynamic programming· Session 033 of 130 75 min

🎯 Stop treating DP as a separate discipline. Write the plain recursion, decorate it with a cache, then mechanically convert it to a table — and know why each step is safe.

Series: LeetCode — From Basics to Interview-Ready · Session 33 / 65 · Phase 2 · Dynamic programming

Why this session exists

Most people who say "I'm bad at DP" are actually bad at starting DP. They stare at the problem trying to intuit the table dimensions and the transition, get nothing, and conclude the topic is beyond them. The table is the last step, not the first.

There is a mechanical path from "I don't know how to do this" to a working bottom-up solution, and it has three stops:

Write the brute-force recursion. Ignore efficiency entirely. Just answer: what smaller version of this problem would let me answer the current one?
Add @lru_cache. If the recursion has overlapping subproblems, this alone takes it from exponential to polynomial. One line. You are now done, in the sense that it will pass.
Convert to a table if you need the constant factor or the interviewer asks. This is a mechanical transformation, not a new act of insight.

That is the whole method. This session establishes it on the simplest possible problems so that when you hit hard DP in sessions 36 and 37, the process is automatic and only the recursion itself requires thought.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

@lru_cache(maxsize=None)
def f(i): ...            — the memoised recursion
then: dp = [0]*(n+1)     — the same thing as a table

Concretely: write Climbing Stairs three ways. Plain recursion, memoised recursion, bottom-up array. Then reduce the array to two variables.

What wobbles: the base cases. f(0) and f(1) for Climbing Stairs both return 1, and getting either wrong shifts the entire sequence by one position — the answer is off by exactly one Fibonacci index, which looks like a small bug and is a total wrong answer.

Pattern anatomy

The shape of problem that summons DP: an optimal or countable answer built from smaller instances of the same question, where the same smaller instance is asked more than once. Both halves matter. Recursion on smaller instances alone is just recursion — merge sort has that and is not DP. The repetition is what makes caching pay.

The invariant, which is the definition of optimal substructure: the answer to a subproblem does not depend on how you arrived at it. f(5) is the same number whether you reached it from f(6) or f(7). That is exactly the property that makes a cache correct — if the answer depended on the path, a single cached value could not serve both callers.

The three forms, on Climbing Stairs. Plain recursion:

def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)      # O(2^n): recomputes everything

Memoised, which is the same function plus one decorator:

from functools import lru_cache
 
def climb(n):
    @lru_cache(maxsize=None)
    def f(i):
        if i <= 1:
            return 1
        return f(i - 1) + f(i - 2)
    return f(n)                              # O(n) time, O(n) space

Bottom-up table, the mechanical conversion:

def climb(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1                        # base cases become initial values
    for i in range(2, n + 1):                # order: dependencies before dependents
        dp[i] = dp[i - 1] + dp[i - 2]        # recursive body becomes assignment
    return dp[n]

Space-optimised, because dp[i] only ever reads two cells back:

def climb(n):
    a, b = 1, 1                              # a = f(i-2), b = f(i-1)
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b                                 # O(1) space

The conversion from memo to table is three mechanical rules, and they are worth stating explicitly because they never change:

Base cases become initial array values. if i <= 1: return 1 becomes dp[0] = dp[1] = 1.
The recursive body becomes an assignment. return f(i-1) + f(i-2) becomes dp[i] = dp[i-1] + dp[i-2].
The loop order must satisfy dependencies. If dp[i] reads dp[i-1], iterate i ascending. If it reads dp[i+1], iterate descending. This is the only step requiring any thought at all.

The cue

You are looking at a DP problem when the statement contains one of these tells:

"How many ways to..." — counting distinct paths, decodings, or arrangements. Climbing Stairs, Decode Ways, Unique Paths.
"Minimum / maximum cost, sum, length, profit" over a sequence of choices. Not a greedy maximum over independent items — a maximum where earlier choices constrain later ones.
"Can you reach / can you form / is it possible" with a target. Word Break, Jump Game, Partition Equal Subset Sum.
A recursion you can write immediately whose branches obviously overlap. This is the real test. Sketch the recursion tree two levels deep; if the same argument appears twice, you have DP.
Constraints around n <= 1000 to n <= 10^5 combined with an exponential-looking brute force. That gap between what brute force costs and what the constraints allow is the problem-setter telling you to cache.

The negative cue: if subproblems do not repeat, caching is pure overhead. Merge sort recurses on halves and never sees the same range twice — adding a cache would slow it down and use memory for nothing. Overlap is the requirement, not recursion.

Guided solve

Climbing Stairs. You are climbing a staircase of n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

Step one: write the recursion. Ask the only question that matters — what is the last thing that happened? To arrive at step n, your final move was either a 1-step from n−1 or a 2-step from n−2. Those two cases are exhaustive and mutually exclusive, so the counts add.

def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)

Base cases. climb(1) = 1 is obvious: one way, a single step. climb(0) = 1 is the one people get wrong. There is exactly one way to climb zero steps — do nothing. The empty sequence is a valid sequence. If you set climb(0) = 0 the whole recurrence shifts and you get the wrong Fibonacci index.

Step two: notice the overlap. Draw the tree for n = 5. climb(5) calls climb(4) and climb(3). climb(4) calls climb(3) and climb(2). climb(3) now appears twice, and each occurrence expands its own full subtree. The total node count follows the Fibonacci growth, which is O(φ^n) with φ ≈ 1.618 — exponential. Meanwhile there are only n distinct arguments. That gap between "number of calls" and "number of distinct arguments" is the definition of overlapping subproblems, and it is exactly what a cache eliminates.

Step three: cache it.

from functools import lru_cache
 
@lru_cache(maxsize=None)
def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)

Two lines added, complexity now O(n) time and O(n) space. Each of the n distinct arguments is computed once; every subsequent call is a dict lookup.

Step four: convert to a table. Apply the three rules above and you get the array version, then the two-variable version. Both are shown in the anatomy section.

The final result is O(n) time, O(1) space, and the sequence is Fibonacci — climb(n) equals the (n+1)-th Fibonacci number. Noticing that is a nice touch but it is not the point. The point is that you got there by a fixed procedure and would have got there on a problem where the answer was not a famous sequence.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

Fibonacci Number — write all four forms: plain, memoised, table, two-variable. Time yourself on the conversions specifically. This should take under five minutes total once the procedure is automatic.
Min Cost Climbing Stairs — the twist is that you may start at index 0 or index 1, and you pay the cost of the step you leave. Get the base cases right before writing the loop; that is where every wrong answer on this problem comes from.

If both land early, do Decode Ways. Same 1D shape, but the transition has validity conditions — a two-digit decode is only legal if the pair is between 10 and 26, and a single-digit decode is illegal if the digit is 0. It is the natural next step up.

Common failure modes

Wrong base case for the empty input. f(0) = 1 for counting problems (one way to do nothing) but f(0) = 0 for "minimum steps" problems (zero cost). Getting it wrong shifts every value and the bug is invisible on small inputs where the answer happens to coincide.

Caching a function that takes a mutable argument. @lru_cache requires hashable arguments. Passing a list raises TypeError: unhashable type. Convert to a tuple, or index into a closed-over list instead of passing it.

Caching something with no overlap. Adds memory and a hash lookup per call for zero benefit. Verify overlap by sketching the tree before reaching for the decorator.

Wrong loop direction in the table version. If dp[i] depends on dp[i-1] you must iterate ascending, otherwise you read an uninitialised zero. This is silent and produces a plausible-looking wrong number.

Off-by-one in the array length. dp = [0] * n when you need to index dp[n]. Allocate n + 1 when the state ranges over 0 to n inclusive.

Space-optimising before the table is correct. The two-variable form is unreadable while debugging. Get dp[] right, verify it, then collapse. Collapsing first means debugging two things at once.

Common misconception

✗ What most people think

Dynamic programming is a fundamentally different technique from recursion, with its own way of thinking that I have to learn separately.

Why the myth is so sticky

DP is recursion plus a cache. Top-down memoisation is literally the same function with a decorator, and bottom-up is a mechanical rewrite of that memoised function with the call stack replaced by an explicit loop. Every DP solution has an equivalent recursion, and the recursion is almost always easier to derive because it only asks 'what is the last thing that happened'. People who find DP hard are usually trying to invent the table directly, skipping the step where the actual thinking happens. Write the recursion first, always — even when you know the table.

From first principles

1
Because the answer to a subproblem is determined entirely by its arguments and not by the path taken to reach it, the same arguments always produce the same result.
2
Because that holds, storing the result the first time and returning it thereafter cannot change any answer — memoisation is provably safe, not merely usually safe.
3
Because the total work becomes the number of DISTINCT subproblems multiplied by the cost of one transition, the complexity is determined by counting states, not by counting calls.
4
Because a memoised recursion computes each state exactly once in an order dictated by its dependencies, replaying that order in an explicit loop computes the same values without the call stack.
5
Because each state in a linear recurrence reads only a bounded window of earlier states, the full array can be collapsed to that window's size.
6
Therefore the testable prediction is that plain recursive fib(40) takes seconds while the memoised version returns instantly, and both return 102334155 — the speedup is asymptotic, from O(φ^n) to O(n), not a constant factor.

Mental model

A ledger on the desk beside you. Every time you finish computing something you write the answer down next to its inputs. When a question comes back, you read the ledger instead of doing the work again. The table version is the same ledger, filled in from the top rather than on demand.

🔔 Fires when you see

Fires when you sketch a recursion tree two levels deep and see the same argument appear in more than one place.

The tradeoff

Top-down memoisation (@lru_cache)

+ you gain One line on top of a recursion you already wrote; computes only the states actually reachable, which can be far fewer than all of them; base cases stay explicit and readable

− you pay Recursion depth can exceed Python's 1000-frame limit; per-call hashing overhead; harder to space-optimise

Bottom-up table

+ you gain No stack limit; lower constant factor; opens the door to rolling-array space reduction

− you pay You must work out a valid fill order yourself; computes every state including unreachable ones; base cases become array initialisation and are easier to get subtly wrong

Space-optimised rolling variables

+ you gain O(1) space; fastest of the three in practice

− you pay Nearly unreadable while debugging; impossible when the answer requires reconstructing the actual path, not just its value

What a senior engineer actually does

Memoise first, always — it is the fastest route from a correct recursion to a passing submission. Convert to bottom-up when the recursion depth may exceed roughly 1000, or when the interviewer asks for iterative. Space-optimise only after the table version is verified correct, and never when you need to reconstruct the chosen path.

Complexity

The universal DP complexity formula: time = (number of distinct states) × (cost of one transition), and space = (number of states you must keep).

For Climbing Stairs the states are i from 0 to n, so n + 1 states. Each transition is one addition, O(1). Total O(n) time.

Space is where the three forms differ. Memoised: O(n) for the cache plus O(n) for the recursion stack. Table: O(n) for the array, no stack. Rolling variables: O(1).

The un-memoised recursion is O(φ^n) where φ = (1+√5)/2 ≈ 1.618, because the call count itself follows the Fibonacci recurrence. At n = 40 that is roughly 300 million calls; at n = 50 it is around 40 billion. This is why the memo is not an optimisation but the difference between working and not working.

State-counting is the skill to build here. When you hit 2D problems in session 39, the states are (i, j) pairs so the count is O(m·n), and if the transition scans a row the cost per transition is O(n) giving O(m·n²) overall. Getting into the habit of stating complexity as states × transition means you will never have to guess.

Quick recall · click to reveal

★ = stretch question

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

cold — solved unaided, first attempt clean → next review in 60 days
warm — solved but slowly or with a stumble → 21 days
hint — needed a nudge to get started → 7 days
failed — could not produce a working solution → 2 days, then 7 days

Climbing Stairs enters the queue, but the thing actually being reviewed is the procedure, not the problem. When it comes back up, do not just write the answer — write all four forms in order and time the conversions. The procedure is what transfers to hard DP; the answer to Climbing Stairs transfers nowhere.

Key points