From Recursion to DP

Dynamic programming (DP) is not a new algorithm — it’s a fix for a specific disease that plain recursion catches: solving the same subproblem over and over again. Once you can point at the repeated work in a recursion tree, turning it into DP is mechanical.

What you’ll learn

The two signs that mean a problem can be solved with DP: optimal substructure and overlapping subproblems.
How to see overlapping subproblems in a recursion tree.
Memoization (top-down) — caching a slow recursive function with functools.lru_cachefunctools.lru_cache and with a manual dictionary.
Tabulation (bottom-up) — building the answer iteratively from the smallest subproblems up.
How to design a DP state: what does dp[i]dp[i] (or dp[i][j]dp[i][j]) actually mean?
Why the fix takes an algorithm from exponential time to polynomial time.

The two signs of a DP problem

A problem is a candidate for dynamic programming when it has both:

Optimal substructure — the optimal answer to the whole problem can be built from optimal answers to its subproblems. If the best way to climb nn stairs is built from the best ways to climb n - 1n - 1 and n - 2n - 2 stairs, that’s optimal substructure.
Overlapping subproblems — naive recursion solves the same subproblem multiple times. If fib(n - 2)fib(n - 2) gets recomputed from scratch inside both the fib(n - 1)fib(n - 1) branch and the fib(n)fib(n) call itself, that’s overlapping subproblems.

If a problem only has optimal substructure but no repeated subproblems (e.g. plain binary search), memoizing it buys nothing — there’s nothing to reuse. DP earns its keep specifically when the same smaller input shows up again and again.

Seeing the repeated work

Take the textbook example: naive recursive Fibonacci.

naive_fib.py

call_count = 0
 
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
 
print("fib(10) =", fib(10))
print("total calls made:", call_count)

naive_fib.py

call_count = 0
 
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
 
print("fib(10) =", fib(10))
print("total calls made:", call_count)

fib(10)fib(10) alone makes 177 calls to compute a single number that has only 11 distinct inputs (fib(0)fib(0) through fib(10)fib(10)). Almost every call is redundant. The recursion tree below shows why: fib(3)fib(3) gets fully recomputed twice, and fib(2)fib(2) gets fully recomputed three times, just to answer fib(5)fib(5).

diagram Recursion tree for fib(5) -- the same subtrees get rebuilt repeatedly mermaid

  graph TD
    N0["fib(5)"] --> N1["fib(4)"]
    N0 --> N2["fib(3)"]
    N1 --> N3["fib(3)"]
    N1 --> N4["fib(2)"]
    N2 --> N5["fib(2)"]
    N2 --> N6["fib(1)"]
    N3 --> N7["fib(2)"]
    N3 --> N8["fib(1)"]
    N4 --> N9["fib(1)"]
    N4 --> N10["fib(0)"]
    N5 --> N11["fib(1)"]
    N5 --> N12["fib(0)"]
    N7 --> N13["fib(1)"]
    N7 --> N14["fib(0)"]

fib(3)fib(3) appears as its own fully-expanded subtree at both N2N2 and N3N3; fib(2)fib(2) is rebuilt from scratch at N4N4, N5N5, and N7N7. Every one of those repeats does identical work and returns an identical answer — the definition of an overlapping subproblem. Cache the answer the first time, and every later call becomes a lookup.

Memoization: top-down DP

Memoization keeps the exact same recursive shape, but the first time a subproblem is solved, its answer is stashed in a cache. Every later call with the same argument returns instantly.

Option 1 — functools.lru_cachefunctools.lru_cache. The least code: one decorator turns any pure function into a memoized one.

fib_lru_cache.py

from functools import lru_cache
 
call_count = 0
 
@lru_cache(maxsize=None)
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
 
print("fib(10) =", fib(10))
print("total calls made:", call_count)   # only 11 -- one per distinct n

fib_lru_cache.py

from functools import lru_cache
 
call_count = 0
 
@lru_cache(maxsize=None)
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
 
print("fib(10) =", fib(10))
print("total calls made:", call_count)   # only 11 -- one per distinct n

Option 2 — a manual dictionary. Same idea, spelled out explicitly — useful when the cache key isn’t a simple hashable argument, or when you want full control over what gets stored.

fib_manual_memo.py

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]              # cache hit -- skip the recursion entirely
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)   # cache the answer before returning
    return memo[n]
 
 
print(fib(10))
print(fib(50))   # instant -- naive recursion here would never finish

fib_manual_memo.py

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]              # cache hit -- skip the recursion entirely
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)   # cache the answer before returning
    return memo[n]
 
 
print(fib(10))
print(fib(50))   # instant -- naive recursion here would never finish

Both versions check “have I already solved this exact subproblem?” before doing any recursive work. That single check is what collapses the exponential tree above into a straight line of 11 unique calls.

Tabulation: bottom-up DP

Tabulation flips the direction: instead of starting from nn and recursing down, start from the smallest subproblems and build up to nn in a loop. There’s no recursion, no call stack, and no risk of hitting Python’s recursion limit on large inputs.

fib_tabulation.py

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # build the answer from smaller ones already known
    return dp[n]
 
 
print(fib(10))
print(fib(50))

fib_tabulation.py

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # build the answer from smaller ones already known
    return dp[n]
 
 
print(fib(10))
print(fib(50))

dp[i] = \begin{cases} i & i \le 1 \\ dp[i-1] + dp[i-2] & i > 1 \end{cases}

Memoization and tabulation compute the exact same values — the choice is usually about style: memoization mirrors the natural recursive definition (easier to derive from a brute force), tabulation avoids recursion overhead and stack limits (usually a little faster in Python).

From exponential to polynomial

Approach	Time	Space
Naive recursion	$O(2^n)$	$O(n)$ call stack
Memoization (top-down)	$O(n)$	$O(n)$ cache + $O(n)$ call stack
Tabulation (bottom-up)	$O(n)$	$O(n)$ table (often reducible to $O(1)$ )

Caching turns “recompute every branch” into “compute each distinct subproblem exactly once.” With only n + 1n + 1 distinct inputs to Fibonacci (00 through nn), and each one doing $O(1)$ work beyond its cached recursive calls, the total work drops from exponential to linear — the same pattern repeats across every DP problem you’ll meet next.

Practice — real LeetCode problems

These three are the smallest complete DP problems on the site. Every harder DP you meet later is one of these with a bigger state, so get the shape into your fingers here: define the state, write the recurrence, name the base cases.

LC 509 — Fibonacci Number · Easy

Problem. F(0) = 0F(0) = 0, F(1) = 1F(1) = 1, and F(n) = F(n-1) + F(n-2)F(n) = F(n-1) + F(n-2) for n > 1n > 1. Return F(n)F(n).

Constraints. 0 <= n <= 300 <= n <= 30.

Examples. n = 2n = 2 gives 11 · n = 3n = 3 gives 22 · n = 4n = 4 gives 33

Editorial · approach, complexity, follow-ups

Naive recursion here is $O(\varphi^n)$ — roughly $1.6^n$ — because fib(n-2)fib(n-2) is recomputed inside fib(n-1)fib(n-1). The call tree for fib(5)fib(5) already evaluates fib(2)fib(2) three times. Memoizing collapses it to $O(n)$ time and $O(n)$ space; iterating bottom-up gives $O(n)$ time and $O(1)$ space.

Time $O(n)$ . Space $O(1)$ .

n = 0n = 0 and n = 1n = 1 are the base cases, and they are the only inputs where the loop must not run. Returning nn covers both at once.
range(n - 1)range(n - 1) is the count that trips people up. After the loop body runs once, bb holds F(2)F(2); after n - 1n - 1 runs it holds F(n)F(n). Trace n = 2n = 2 by hand before trusting it.

Follow-ups you should expect: “Compute F(10**6)F(10**6) mod 10**9 + 710**9 + 7?” — same loop, take the modulus each step. “Faster than linear?” — matrix exponentiation of [[1,1],[1,0]][[1,1],[1,0]] gives $O(\log n)$ ; the closed-form Binet formula is $O(1)$ but loses precision past about n = 70n = 70. “Why not functools.lru_cachefunctools.lru_cache on the recursion?” — perfectly fine and it is the fastest thing to write in an interview, but it costs $O(n)$ stack depth and Python’s default recursion limit is 1000.

LC 70 — Climbing Stairs · Easy

Problem. You climb a staircase of nn steps, taking either 1 or 2 steps at a time. In how many distinct ways can you reach the top?

Constraints. 1 <= n <= 451 <= n <= 45.

Examples. n = 2n = 2 gives 22 (1+1, 2) · n = 3n = 3 gives 33 (1+1+1, 1+2, 2+1)

Editorial · approach, complexity, follow-ups

The whole problem is the sentence “the last move was either a 1 or a 2.” Partitioning the paths by their final move is the standard way to derive a DP recurrence, and it is what an interviewer wants to hear out loud.

Time $O(n)$ . Space $O(1)$ .

ways(0) = 1ways(0) = 1, not 0. There is exactly one way to stand still: take no steps. Getting this wrong shifts every answer.
n = 1n = 1 must return 1, which is why the loop runs n - 1n - 1 times rather than nn.
n = 45n = 45 is the constraint ceiling and the answer is about $1.8 \times 10^9$ — comfortably inside a 32-bit signed int, which is exactly why LeetCode caps it there.

Follow-ups you should expect: “Steps of 1, 2, or 3 (LC 1137)?” — sum the previous three. “Any set of allowed step sizes?” — an inner loop over the sizes; that is unbounded knapsack counting. “Each step has a cost, minimise it?” — that is the next problem. “Count the paths themselves?” — exponentially many, so backtracking, not DP.

LC 746 — Min Cost Climbing Stairs · Easy

Problem. cost[i]cost[i] is the cost of stepping off stair ii. You may start at index 0 or index 1, and from a stair you may climb one or two stairs. Return the minimum cost to reach the top (one past the last index).

Constraints. 2 <= len(cost) <= 10002 <= len(cost) <= 1000, 0 <= cost[i] <= 9990 <= cost[i] <= 999.

Examples. cost = [10,15,20]cost = [10,15,20] gives 1515 (start at index 1, pay 15, jump two to the top) · cost = [1,100,1,1,1,100,1,1,100,1]cost = [1,100,1,1,1,100,1,1,100,1] gives 66

Editorial · approach, complexity, follow-ups

This is Climbing Stairs with weights, and it is the first problem on the site where the wording of the state decides whether the code is clean or a mess.

Two defensible definitions:

dp[i]dp[i] = cost to stand on stair ii. Base dp[0] = dp[1] = 0dp[0] = dp[1] = 0, and you add cost[j]cost[j] when you leave stair jj. The top is index len(cost)len(cost), so the loop runs to len(cost)len(cost) inclusive and the answer is dp[len(cost)]dp[len(cost)].
dp[i]dp[i] = cost to reach the top from stair ii. Base dp[n-1] = cost[n-1]dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]dp[n-2] = cost[n-2], fill backwards, answer min(dp[0], dp[1])min(dp[0], dp[1]).

Both are correct. Pick one and stay in it — half-mixing them is the single most common bug on this problem.

Time $O(n)$ . Space $O(1)$ .

The top is not the last index. [10,15,20][10,15,20] answers 15, not 30: you start on index 1, pay 15, and jump straight past index 2. If you get 30 you are treating the last stair as the destination.
Two free starts means dp[1] = 0dp[1] = 0, not cost[0]cost[0].
[5,5][5,5] answers 5: start on stair 0, pay 5, jump two to the top. Length 2 is the minimum input and worth tracing.

Follow-ups you should expect: “Which stairs did you use?” — store a parent pointer per index and walk back. “Steps of up to kk?” — a sliding-window minimum over the last kk values keeps it $O(n)$ instead of $O(nk)$ (LC 1696 is exactly this). “Costs may be negative?” — the DP is unchanged; only a greedy would break. “Maximise instead?” — swap minmin for maxmax; the recurrence does not care.

LeetCode problem set

#	Problem	Difficulty	The twist
509	Fibonacci Number	Easy	The exact template above
70	Climbing Stairs	Easy	Same recurrence, different story (next lesson)
1137	N-th Tribonacci Number	Easy	The same idea with three previous terms instead of two
746	Min Cost Climbing Stairs	Easy	Optimal substructure with a small twist on the transition
118	Pascal’s Triangle	Easy	Each row is built from the row above it, a 2D warm-up for the next lessons

Recap

DP applies when a problem has optimal substructure (the best answer is built from optimal answers to subproblems) and overlapping subproblems (naive recursion solves the same subproblem repeatedly).
Memoization (top-down) keeps the natural recursive shape and adds a cache — functools.lru_cachefunctools.lru_cache for the quick version, a manual dict when you need control.
Tabulation (bottom-up) builds the answer iteratively from the smallest subproblems, with no recursion or call stack.
Designing a DP state starts with one sentence: ”dp[i]dp[i] means …“. The recurrence follows from asking how dp[i]dp[i] combines smaller, already-known states.
The payoff: exponential $O(2^n)$ naive recursion collapses to polynomial $O(n)$ once every distinct subproblem is solved exactly once.

Next: One Dimensional DP — applying this exact recipe to Climbing Stairs, House Robber, Coin Change, and Decode Ways, where the state is a single index.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

From Recursion to DP

What you’ll learn

The two signs of a DP problem

Seeing the repeated work

Memoization: top-down DP

Tabulation: bottom-up DP

From exponential to polynomial

Practice — real LeetCode problems

LC 509 — Fibonacci Number · Easy

LC 70 — Climbing Stairs · Easy

LC 746 — Min Cost Climbing Stairs · Easy

LeetCode problem set

Recap

Was this page helpful?