L33 · DP I — Recognising Overlapping Subproblems

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

Watch first

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:

1. Write the brute-force recursion. Ignore efficiency entirely. Just answer: what smaller version of this problem would let me answer the current one?
2. 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.
3. 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:

1. "How many ways to..." — counting distinct paths, decodings, or arrangements. Climbing Stairs, Decode Ways, Unique Paths.
2. "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.
3. "Can you reach / can you form / is it possible" with a target. Word Break, Jump Game, Partition Equal Subset Sum.
4. 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.
5. 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.

Worked variant — House Robber, all three stops in one file

Climbing Stairs is Fibonacci in disguise and can be pattern-matched without understanding. House Robber cannot: there is a real choice at each index, which is what makes it the better demonstration of the ladder.

Stop 1 — the brute-force recursion. Ask only: what is the choice at index i?

def rob_brute(nums):
    def best_from(i):
        # STATE: 'the most I can rob from index i onward'.
        # Naming the state in a sentence is the actual work here.
        if i >= len(nums):
            return 0                          # base case: nothing left
        take = nums[i] + best_from(i + 2)     # rob it -> must skip i+1
        skip = best_from(i + 1)               # leave it -> i+1 is available
        return max(take, skip)
    return best_from(0)

Exponential, because best_from(i + 2) is reached from both i and i + 1. That double reachability is the overlap — it is not an abstract property, it is a specific arrow you can point at in the tree.

Stop 2 — memoise. One decorator, no restructuring.

from functools import lru_cache
 
def rob_memo(nums):
    @lru_cache(maxsize=None)              # args must be hashable: i is an int, fine
    def best_from(i):
        if i >= len(nums):
            return 0
        return max(nums[i] + best_from(i + 2), best_from(i + 1))
    return best_from(0)                    # O(n) time, O(n) space + recursion stack

The cache key is the argument tuple. This is why nums is closed over rather than passed — a list argument is unhashable and lru_cache would raise. Passing a tuple works but makes every key carry the whole array, which is slow and wasteful.

Stop 3 — tabulate, then shrink. The conversion is mechanical: reverse the recursion's direction, and read the base case off the same lines.

def rob_table(nums):
    n = len(nums)
    dp = [0] * (n + 2)                     # +2 so dp[i+2] never runs off the end
    for i in range(n - 1, -1, -1):         # recursion went forward, so table goes backward
        dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])
    return dp[0]
 
def rob_o1(nums):
    # The recurrence only ever reads two positions ahead, so keep two variables.
    take_next, skip_next = 0, 0            # dp[i+1], dp[i+2]
    for x in reversed(nums):
        take_next, skip_next = max(x + skip_next, take_next), take_next
    return take_next                        # O(n) time, O(1) space

The rule for the loop direction: the table is filled in the reverse of the recursion's argument movement. The recursion moved from i toward n, so the table fills from n back to 0. Get this backwards and you read cells that have not been written yet — which in Python is a silent zero rather than a crash, and therefore a wrong answer rather than an error.

The rule for space reduction: count how far back the recurrence reaches. Two positions here, so two variables. That is the entire justification, and it is why you should always be able to state the reach.

Memory hook — "recurse, cache, roll"

Three words for the three stops, in the order you are allowed to do them:

• Recurse — write the honest brute force and do not think about efficiency at all. The only question is: what smaller version of this answers the current one? Say the state as a sentence — "the most I can rob from index i onward" — before you type the signature. If you cannot say the sentence, no table will save you.
• Cache — add @lru_cache. If the recursion overlapped, you are now polynomial, and in an interview that is a passing solution you can defend. Never skip this to jump to a table; the table is derived from the recursion, so producing it first means guessing.
• Roll — convert to a table, then roll the table down to the recurrence's reach. Fill direction is the reverse of the recursion's movement; variable count equals how far back the recurrence looks.

The peg for whether DP applies at all is "a tree with repeats" — draw two levels of the recursion tree and look for the same argument appearing twice on different branches. Repeats mean memoise. No repeats means it is divide and conquer, and a cache buys you nothing but memory.

What interviewers actually ask

These are the DP problems used as entry points. They are chosen because they are gettable, which means a stumble here is read as a topic gap rather than bad luck.

• 70 · Climbing Stairs (Easy) — Amazon, Google, Adobe. Probing whether you can name the recurrence. Follow-up: "you can climb 1, 2, or 3 steps" — the recurrence gains a term and nothing else changes.
• 198 · House Robber (Medium) — Amazon, Google, Meta, Microsoft. Probing take-versus-skip. Follow-up: 213 · House Robber II, houses in a circle — run the linear version twice, excluding the first house then the last.
• 746 · Min Cost Climbing Stairs (Easy) — Amazon, Google. Probing base-case care; the two possible starting positions are where this one is lost.
• 322 · Coin Change (Medium) — Amazon, Google, Meta, Uber. Probing unbounded choice. Follow-up: "count the number of ways instead" — that is 518, and the loop nesting order flips, which is the classic trap.
• 139 · Word Break (Medium) — Amazon, Google, Meta, Bloomberg. Probing whether you see a string index as a DP state at all.
• 91 · Decode Ways (Medium) — Meta, Amazon, Microsoft. Probing edge cases around zeros, which no amount of recurrence elegance rescues.
• 279 · Perfect Squares (Medium) — Google, Amazon. Probing the same unbounded-coin shape wearing a number-theory costume.

The escalation to watch: "now reconstruct the actual choice, not just the optimal value." That needs a parent-pointer array alongside the DP table, and it is the follow-up most people have never rehearsed.

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.

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.