DP I — Recognising Overlapping Subproblems

Review boundary and corrected contracts

Memoization requires a sufficient cache key and stable function meaning. Overlap determines its benefit, not the correctness of caching. Pure counting and feasibility recurrences are DP too. The rolling House Robber variables are next-position values, not independent take/skip states.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: 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 Production-Ready · Session 33 / 65 · Phase 2 · Dynamic programming

Watch first

Optional original video routes: Climbing Stairs, memoization → tabulation, and overlapping-subproblem intuition. The self-contained task here is to draw the calls from climb(5) and mark both occurrences of climb(3) before reading the solution.

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(maxsize=None) to a terminating recurrence with a sufficient, hashable state. Each reachable state is then computed once in this single-threaded use. Count states and work per state: overlap alone does not guarantee polynomial time, bounded memory, or a safe recursion depth. A subset-mask state space can still have 2^n states.
3. Convert to a table if you need the constant factor or a reviewer 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. For nonnegative integer n, f(0) and f(1) for Climbing Stairs both return 1. Changing only f(0) to 0 gives F_n rather than F_(n+1); other incorrect initial values need not produce a simple index shift.

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.

A reusable state must contain everything that affects its future answer. That sufficiency is distinct from optimal substructure (how optimal subanswers combine) and overlap (whether states are requested repeatedly).

The forms below assume nonnegative integer n. Negative input is outside the contract, even though these short functions return a number for it. 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. Large inputs combined with exponential brute force. Look for a smaller state space, then count it. Constraints alone do not establish that memoization will fit; greedy, search or a different state may be needed.

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 motivates reuse; state sufficiency and a terminating dependency structure make this memoization correct.

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: O(n) arithmetic operations and O(n) cached values plus stack frames. For n ≥ 2, the reachable arguments are 0 through n, so n + 1 states; subsequent requests use the cache.

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.

Matrix exponentiation or fast doubling reduces the number of arithmetic steps to O(log n), but the integers grow with n: this is not an O(log n) bit-time bound. Binet's formula is exact symbolically; ordinary floating-point evaluation is not a reliable exact-integer algorithm for large n. First derive the linear recurrence, then discuss these alternatives if the input scale warrants them.

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. Derive the zero-cost starts before writing the loop; transitions and indexing still need checking.

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

Borrowing a base case without reading the state. Here climb(0) = 1 counts the empty sequence. A minimum-cost state for an already reached target can start at 0; an unreachable state needs infinity. Counting nonempty objects may instead give zero. Derive the value from the precise question, not from the word "count" or "cost".

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.

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

Why: For the acyclic recurrences here, memoization reuses state answers and tabulation evaluates the same dependency graph explicitly. Deriving the recursion first is a useful learning exercise, not a requirement to submit or execute an exponential program. A table derived directly from a clear state and dependency proof is equally valid.

Steps 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.

Steps 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.

Steps 3: With an unbounded cache, count distinct states and the total work to compute each state, including all candidate transitions and key operations. Their sum bounds the work; states times maximum work per state is a convenient upper bound.

Steps 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.

Steps 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.

Steps 6: For Fibonacci with F_0 = 0 and F_1 = 1, both recurrences yield F_40 = 102334155. Memoization changes the arithmetic-operation count from exponential to linear; elapsed seconds depend on the runtime. Climbing Stairs uses different bases and gives F_41 = 165580141 at n = 40.

Picture: 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.

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

Name: Top-down memoisation (@lru_cache)

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

Cost: Recursion can exceed the interpreter's configured limit (sys.getrecursionlimit()); caching does not remove stack depth. Hashing and cache storage also cost work and memory.

Name: Bottom-up table

Gain: No stack limit; lower constant factor; opens the door to rolling-array space reduction

Cost: 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

Name: Space-optimised rolling variables

Gain: A constant number of stored DP values; avoids retaining the full table

Cost: Harder to inspect while debugging; these scalars alone do not retain reconstruction choices. Keep a table or decision record, or accept recomputation.

Pick: Derive the state and recurrence first. Memoize when reachable-state count and stack depth fit; tabulate when recursion depth is unsafe. Roll the table only after checking dependencies and deciding how any requested path will be recovered.

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. An integer tuple is hashable, but including the whole input in every key adds hashing work; cache keys retain references, not necessarily a fresh array copy per state. The closed-over list must remain unchanged during a solve, and this nested cache is fresh for each call.

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 — use @lru_cache(maxsize=None) when reuse helps, then count reachable states and per-state work. Polynomially many states with polynomial work give a polynomial bound; overlap alone does not. A directly derived table is also valid.
• 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 suggest memoization when keys are sufficient and dependencies terminate. No repeats means a cache saves no repeated work in that execution; it does not by itself classify every recursion as divide and conquer.

What reviewers 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) — Practice selection. 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) — Practice selection. 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) — Practice selection. Probing base-case care; the two possible starting positions are where this one is lost.
• 322 · Coin Change (Medium) — Practice selection. 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) — Practice selection. Probing whether you see a string index as a DP state at all.
• 91 · Decode Ways (Medium) — Practice selection. Probing edge cases around zeros, which no amount of recurrence elegance rescues.
• 279 · Perfect Squares (Medium) — Practice selection. Probing the same unbounded-coin shape wearing a number-theory costume.

A useful follow-up is: "now reconstruct the actual choice, not just the optimal value." Keep decisions or enough table entries to infer them during backtracking. Parent pointers are one option; recomputation is another time/space tradeoff.

Complexity

The DP accounting rule: time is the sum of the work for all computed states, bounded by states × maximum work per state. Include every candidate transition, not just one edge. Space counts live stored values plus the call stack and other auxiliary data.

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. For this exact climb, C_0 = C_1 = 1 and C_n = C_(n−1) + C_(n−2) + 1, hence C_n = 2F_(n+1) − 1: 331160281 calls at n = 40 and 40730022147 at n = 50. 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.

Self-check (answer follows each question).

Q: What makes state reuse correct and useful here, and what does merge sort lack?

A: The state must determine a stable answer, and the recurrence must combine smaller states correctly. Optimization recurrences use optimal substructure; counting and feasibility use their own valid combinations. Repeated states make caching useful. Merge sort on index ranges has no repeated range calls, so that cache adds no benefit.

Q: Why is climb(0) equal to 1 rather than 0?

A: There is exactly one way to climb zero steps: take no steps at all. The empty sequence is a valid sequence. Setting it to 0 shifts the entire recurrence by one index.

Q: State the three mechanical rules for converting a memoised recursion to a bottom-up table.

A: Base cases become initial array values; the recursive body becomes an assignment to dp[i]; and the loop must run in an order that fills every dependency before its dependent — ascending when dp[i] reads dp[i−1].

Q: What is the general formula for DP time complexity?

A: Sum the work to compute every state, or bound it by number of states times maximum work per state. Climbing Stairs has O(n) states with one addition each, giving O(n) arithmetic operations.

Q: When should you NOT space-optimise a DP down to rolling variables?

A: Do not discard information needed for a requested witness without a recovery plan. A full table, decision records or recomputation can recover choices; the two scalars alone cannot. Verify the table and dependencies before rolling them away.

Q: Why is Θ(φ^n) a tighter call-count bound than O(2^n) for un-memoised Climbing Stairs?

A: C_n = C_(n−1) + C_(n−2) + 1 with C_0 = C_1 = 1 gives Θ(φ^n). O(2^n) is still a valid looser upper bound. Each non-leaf has two children, so the tree is full in that sense, but it is not perfect: the n−2 branch terminates earlier.

Stretch: true

You can now…

• State a DP state as an English sentence before writing the function signature.

• Write the brute-force recursion first, deliberately ignoring efficiency.

• Point at a specific repeated argument in a two-level recursion tree to justify that subproblems overlap.

• Add @lru_cache correctly — hashable arguments only, arrays closed over rather than passed.

• Convert memoisation to a table, filling in the reverse of the recursion's argument movement.

• Reduce table space to O(1) by counting how far back the recurrence reaches.

• Distinguish overlapping subproblems from plain divide and conquer, and say why a cache is useless in the latter.

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.

• Derive a sufficient state and a terminating recurrence; memoization and tabulation evaluate the same dependencies in these examples.

• The recursion question is always 'what is the last thing that happened' — enumerate the exhaustive, mutually exclusive final moves.

• Sketch the tree two levels deep. Repeated arguments mean overlapping subproblems, which means caching pays. No repetition means caching is pure overhead.

• Memo-to-table is three mechanical rules: base cases become initial values, the body becomes an assignment, the loop order follows the dependencies.

• Count work per state across all candidate transitions, and count live values plus stack space.

• Here climb(0) = 1 counts the empty sequence. Other base cases follow their state meanings, not a universal counting/cost rule.

Corrective source notes

• Python 3.14: lru_cache — hashable keys, unbounded maxsize=None, and reuse restrictions; recursion limit — configured interpreter limit, not a portable fixed depth. Freshly checked 2026-10-09.

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.