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_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] (or dp[i][j]) actually mean?
Why the fix takes an algorithm from exponential time to polynomial time.

The cue

You can write a correct recursive solution and it is too slow — and the reason it is slow is that the same argument arrives more than once. That is the entire diagnosis: not “recursion is slow”, but “recursion recomputes”.
The problem asks for a count, a maximum/minimum, or a yes/no reachability, and the answer for input n is built from answers for smaller inputs.
A greedy choice provably fails — you can construct an input where the locally best move forfeits a better global outcome.
The brute force is exponential ( $2^n$ subsets, $2^n$ paths) but the number of distinct states is small — polynomial, or at least tractable. That gap between “paths” and “states” is where the speedup comes from, and it is worth stating out loud.

The reframe: do not try to invent the table. Write the recursion first, name its arguments, and then observe that those arguments are the DP state. Every DP on the following pages was derived that way — dp[i], dp[i][w], dp[mask][i] are just the parameter lists of a recursive function that someone cached.

Reach for something else when subproblems never repeat (plain divide-and-conquer such as binary search or merge sort — memoising buys nothing because nothing is reused), when a greedy is provably optimal (interval scheduling, Huffman), or when the state space is genuinely exponential with no overlap, in which case you need pruning and backtracking rather than a cache.

Visual intuition

The whole page in two traces. First the naive recursion — watch the same subtrees being rebuilt:

recursionfib(6) without memoisation: fib(3) is computed three separate timesO(2^n) calls

call stack

1def fib(n):2    if n <= 1:3        return n4    return fib(n - 1) + fib(n - 2)

n6calls so far1

callfib(6) needs fib(5) and fib(4). Neither is known, so both are computed from scratch — including everything they in turn need.

1/51

Follow the tree left to right and count the nodes labelled fib(3), fib(2), fib(1). Each is a complete subtree rebuilt from scratch, returning an identical answer every time. The tree has 25 nodes for a function with only 7 distinct inputs -- and that ratio is what grows exponentially.

Now the same function with a cache. Same shape, but every repeat is cut off at the root:

recursionfib(10) with memoisation: each distinct input is computed exactly onceO(n) calls

call stack

f10

1from functools import cache2 3@cache                      # the entire fix4def fib(n):5    if n <= 1:6        return n7    return fib(n - 1) + fib(n - 2)

n10cached0calls1

callfib(10) is not cached yet, so it recurses — but only this once. Every later request for fib(10) will be a hit.

1/39

The cache hits terminate immediately rather than expanding. n = 10 fits comfortably here, whereas the naive tree above had to be capped at 6 -- which is itself the demonstration. 177 calls become 19, and nothing about the recursion's logic changed.

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 n stairs is built from the best ways to climb n - 1 and n - 2 stairs, that’s optimal substructure.
Overlapping subproblems — naive recursion solves the same subproblem multiple times. If fib(n - 2) gets recomputed from scratch inside both the fib(n - 1) branch and the 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)

fib(10) alone makes 177 calls to compute a single number that has only 11 distinct inputs (fib(0) through fib(10)). Almost every call is redundant. The recursion tree below shows why: fib(3) gets fully recomputed twice, and fib(2) gets fully recomputed three times, just to answer 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) appears as its own fully-expanded subtree at both N2 and N3; fib(2) is rebuilt from scratch at N4, N5, and N7. 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_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

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

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 n and recursing down, start from the smallest subproblems and build up to n 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))

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

Dry run

Naive fib(5), counting calls. The recursion visits, in order:

fib(5) → fib(4) → fib(3) → fib(2) → fib(1), fib(0) … and then rebuilds fib(1), fib(2), fib(3), fib(2), fib(1), fib(0) again on the way back out.

`n`	distinct inputs	calls made	ratio
5	6	15	2.5×
10	11	177	16×
20	21	21,891	1,042×
30	31	2,692,537	86,856×

The ratio is the whole story, and it is not a constant — it grows exponentially. Six distinct inputs cost 15 calls; 31 distinct inputs cost 2.7 million. Every extra unit of n roughly multiplies the redundancy.
fib(2) is computed three times in fib(5) and 5 times in fib(6) — its own subtree rebuilt in full each time, always returning 1.

The same call with a cache, tracing what happens at each entry:

step	call	outcome
1	`fib(5)`	miss → compute
2	`fib(4)`	miss → compute
3	`fib(3)`	miss → compute
4	`fib(2)`	miss → compute (bottoms out on `fib(1)`, `fib(0)`)
5	`fib(2)` again — from `fib(4)`	hit, returns immediately
6	`fib(3)` again — from `fib(5)`	hit, returns immediately

Four computations and two hits, against fifteen calls. Three things worth extracting:

Every cache hit prunes an entire subtree, not one call. Step 6’s hit on fib(3) skips what would have been five more calls. That is why the saving compounds.
The number of computations equals the number of distinct states — 6 here, n + 1 in general. This is the sentence that generalises to every DP: total work = number of states × work per state. Memoisation does not make the recursion cleverer; it makes each state happen once.
The recursion’s logic never changed. Same base case, same recursive expression. Two lines of cache bookkeeping — or one @lru_cache decorator — is the entire difference between $O(2^n)$ and $O(n)$ .

Tabulation on the same problem fills dp = [0, 1, 1, 2, 3, 5] left to right. Identical values, identical count of computations — the only difference is that you chose the order (smallest first) instead of letting the recursion discover it.

Complexity

Approach	Time	Space	Notes
Naive recursion	$O(\phi^n) \approx O(1.618^n)$	$O(n)$ call stack	the base is the golden ratio, not 2 — the tree is unbalanced
Memoisation (top-down)	$O(n)$	$O(n)$ cache + $O(n)$ stack	skips unreachable states
Tabulation (bottom-up)	$O(n)$	$O(n)$ table, often $O(1)$	no recursion limit, better constants
Tabulation, rolling	$O(n)$	$O(1)$	when the reach-back is fixed

The general formula, which is the one to carry forward:

$\text{total time} = (\text{number of distinct states}) \times (\text{work per state})$

For Fibonacci that is $n \times O(1) = O(n)$ . For 0/1 knapsack it is $nW$ states × $O(1)$ = $O(nW)$ . For interval DP it is $n^2$ states × $O(n)$ per split = $O(n^3)$ . Counting states and per-state work separately is faster and more reliable than trying to reason about the recursion tree directly.

Caching turns “recompute every branch” into “compute each distinct subproblem exactly once.” With only n + 1 distinct inputs to Fibonacci (0 through n), 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.

The variant map

Every DP shape in this phase is the same three steps — write the recursion, name its parameters, cache it. What changes is only what the parameters are:

Recursion’s parameters	Becomes	Page
`f(i)` — one index	`dp[i]`	1-D DP
`f(i, capacity)`	`dp[i][w]`	2-D DP and knapsack
`f(i, j)` — two sequences	`dp[i][j]`	classic DP: LCS, edit distance
`f(row, col)`	the grid itself	grid DP
`f(left, right)` — a range	`dp[l][r]`, filled by increasing length	interval DP
`f(i, holding)` — a flag	a state machine	DP on stocks
`f(mask)` — a subset	`dp[mask]`	bitmask DP
`f(node)` — returns a tuple	no table; post-order recursion	tree DP
`f(pos, tight, …)` — digits of a bound	`dp[pos][tight][extra]`	digit DP

Choice	Top-down (memoisation)	Bottom-up (tabulation)
Writing it	mechanical — add a cache to working recursion	must derive the fill order yourself
Unreachable states	skipped — a win when the state space is sparse	computed anyway
Recursion limit	dies past ~1000 frames in CPython	none
Constant factors	dict/function-call overhead	tight loops over a list
Space optimisation	hard	easy — rolling rows
Debugging	print on cache miss	print the table

Neither is “the real DP”. Write top-down first, because it is derived rather than invented; convert to bottom-up when you need the space optimisation or the recursion depth is a problem.

Pitfalls

Caching on an incomplete key. Every parameter that affects the answer must be in the cache key. Leaving one out returns a confidently wrong value with no error — this is the same bug as omitting tight in digit DP, and it is the most dangerous mistake in the whole topic.
Caching on a mutable argument. @lru_cache requires hashable parameters, so a list or a set must be converted to a tuple or a frozenset — or, better, replaced by an index or a bitmask. If you find yourself hashing a big structure, the state is probably wrong.
Keeping the cache alive between calls. A self.memo dict on a LeetCode Solution object persists across test cases; if the key does not include everything that varies (the input itself), later cases read earlier answers. Build the cache inside the call.
@lru_cache on a method. It keeps self in the key, which pins the instance in memory and never shares work as you might expect. Cache an inner closure instead.
Recursion depth. A memoised solution over a $10^5$ -element array recurses $10^5$ deep and raises RecursionError. Either sys.setrecursionlimit, or convert to tabulation — the latter is the answer interviewers prefer.
Memoising something with no overlap. Binary search and merge sort have optimal substructure but no repeated subproblems, so a cache adds overhead and saves nothing. Check that the same argument really does recur.
Designing the table before the recursion. Inventing dp[i][j] and hoping the meaning emerges is how people get stuck. Write the recursion, then read off the state.
A base case that does not match the state’s meaning. If dp[i] is “using the first i elements”, then dp[0] is the empty prefix — 1 for a count, 0 for a sum, inf for a minimisation. Guessing here shifts every value.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is the naive recursion slow?”	Whether you can diagnose rather than pattern-match	Not because recursion is slow — because the same argument is computed repeatedly. `fib(5)` makes 15 calls for 6 distinct inputs, and that ratio grows exponentially
“What is the complexity after memoising, and how do you know?”	The general method	Number of distinct states × work per state. For Fibonacci, $n$ states × $O(1)$ = $O(n)$ . That formula is how you compute every DP bound in this phase
“Top-down or bottom-up?”	Judgement, not dogma	Top-down to derive it — the recursion already exists and caching is mechanical. Bottom-up when you need $O(1)$ space or must avoid Python’s recursion limit. Top-down also skips unreachable states, which matters when the space is sparse
“Convert your memoised solution to a table”	Whether you understand the dependency order	The parameters become the indices, and the fill order must ensure every value a cell reads is already computed — smallest index first for 1-D, increasing length for intervals
“How do you choose the DP state?”	The actual skill	Write a correct recursion first. Its parameters are the state. If a parameter does not affect the answer, drop it; if the answer varies with something not in the parameter list, that thing is missing from the state
“Would memoisation help binary search?”	Whether you know the precondition	No. It has optimal substructure but no overlapping subproblems — each call halves into a different range, so nothing is ever reused. DP needs both properties
“Your solution hits Python’s recursion limit”	Practicality	Convert to bottom-up, which has no stack depth; or raise the limit with `sys.setrecursionlimit`, which is a workaround rather than a fix. Say which you would ship
“Is Fibonacci really $O(2^n)$ ?”	Precision	$O(2^n)$ is a valid loose bound; the tight one is $O(\phi^n)$ , $\phi \approx 1.618$ , because the `n-2` branch is a smaller subtree so the tree is not full. The exact call count is $2\,fib(n+1) - 1$

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) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Return F(n).

Constraints. 0 <= n <= 30.

Examples. n = 2 gives 1 · n = 3 gives 2 · n = 4 gives 3

Editorial · approach, complexity, follow-ups

Naive recursion here is $O(\varphi^n)$ — roughly $1.6^n$ — because fib(n-2) is recomputed inside fib(n-1). The call tree for fib(5) already evaluates 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 = 0 and n = 1 are the base cases, and they are the only inputs where the loop must not run. Returning n covers both at once.
range(n - 1) is the count that trips people up. After the loop body runs once, b holds F(2); after n - 1 runs it holds F(n). Trace n = 2 by hand before trusting it.

Follow-ups you should expect: “Compute F(10**6) mod 10**9 + 7?” — same loop, take the modulus each step. “Faster than linear?” — matrix exponentiation of [[1,1],[1,0]] gives $O(\log n)$ ; the closed-form Binet formula is $O(1)$ but loses precision past about n = 70. “Why not functools.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 n steps, taking either 1 or 2 steps at a time. In how many distinct ways can you reach the top?

Constraints. 1 <= n <= 45.

Examples. n = 2 gives 2 (1+1, 2) · n = 3 gives 3 (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) = 1, not 0. There is exactly one way to stand still: take no steps. Getting this wrong shifts every answer.
n = 1 must return 1, which is why the loop runs n - 1 times rather than n.
n = 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] is the cost of stepping off stair i. 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) <= 1000, 0 <= cost[i] <= 999.

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

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] = cost to stand on stair i. Base dp[0] = dp[1] = 0, and you add cost[j] when you leave stair j. The top is index len(cost), so the loop runs to len(cost) inclusive and the answer is dp[len(cost)].
dp[i] = cost to reach the top from stair i. Base dp[n-1] = cost[n-1], dp[n-2] = cost[n-2], fill backwards, answer 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] 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] = 0, not cost[0].
[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 k?” — a sliding-window minimum over the last k 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 min for max; the recurrence does not care.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

5 problems

5 easy0 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

70Climbing StairseasySame recurrence, different story (next lesson)NeetCode 150Blind 75LeetCode Top Interview 150
118Pascal's TriangleeasyEach row is built from the row above it, a 2D warm-up for the next lessons
509Fibonacci NumbereasyThe exact template above
746Min Cost Climbing StairseasyOptimal substructure with a small twist on the transitionNeetCode 150
1137N-th Tribonacci NumbereasyThe same idea with three previous terms instead of two

Self-check

pch.quizTag From recursion to DP — self-check

Naive `fib(5)` makes 15 calls for 6 distinct inputs. What makes that a DP diagnosis rather than just 'recursion is slow'?

pch.quizShowAnswer

B — The ratio of calls to distinct inputs, and the fact that it grows exponentially: 6 inputs cost 15 calls, 31 inputs cost 2.7 million. The same argument is being recomputed — Overlapping subproblems is a property of the problem, not of recursion. Divide-and-conquer recursions like merge sort have no overlap and gain nothing from a cache.
What is the general formula for a DP's time complexity?

pch.quizShowAnswer

B — Number of distinct states × work per state — n × O(1) for Fibonacci, nW × O(1) for knapsack, n² states × O(n) split for interval DP — Counting states and per-state work separately is faster and far more reliable than reasoning about the recursion tree, and it works unchanged for every shape in this phase.
How should you choose a DP state?

pch.quizShowAnswer

B — Write a correct recursion first — its parameters ARE the state. If something changes the answer but is not a parameter, it is missing from the state — Designing the table first is how people get stuck. Deriving it from working recursion is why every page in this phase — knapsack, intervals, bitmask, digit DP — can be presented as the same three steps.
When is top-down (memoisation) the better choice over bottom-up?

pch.quizShowAnswer

B — When you want to derive it mechanically from working recursion, and when the state space is sparse — top-down skips unreachable states that a table would compute anyway — Bottom-up wins on constants, space optimisation, and Python's recursion limit. Neither is the 'real' DP — write top-down to derive, convert when you need what tabulation gives you.
You memoise but leave one parameter out of the cache key. What happens?

pch.quizShowAnswer

B — A cached value computed under different conditions gets reused, so the answer is silently wrong — no crash, no obvious symptom — This is the most dangerous mistake in the topic and it recurs everywhere — omitting `tight` in digit DP is the same bug. Every parameter that affects the answer belongs in the key.
Would memoising binary search help?

pch.quizShowAnswer

B — No — it has optimal substructure but no overlapping subproblems, since each call recurses into a different range. DP requires both properties — Being able to name the case where DP does NOT apply is what makes the two-property test useful rather than decorative.

Recall card

Cue — a correct recursion exists and is too slow because the same argument recurs. Counting, max/min, or reachability, with a greedy that provably fails.
Two required properties — optimal substructure and overlapping subproblems. Without the second, a cache buys nothing (binary search, merge sort).
The method, in three steps — (1) write the recursion, (2) its parameters are the state, (3) cache it. Never design the table first.
Complexity — states × work per state. $n \times O(1)$ for Fibonacci, $nW$ for knapsack, $n^2 \times O(n)$ for interval DP.
Top-down — mechanical, skips unreachable states, dies at CPython’s ~1000 frames. Bottom-up — you choose the fill order, no depth limit, and space collapses to rolling rows.
Every parameter that affects the answer must be in the cache key — omitting one gives a silently wrong answer.
Base cases follow from the state’s meaning — dp[0] on an empty prefix is 1 for a count, 0 for a sum, inf for a minimisation.
Naive Fibonacci is $O(\phi^n)$ , exactly $2\,fib(n+1) - 1$ calls; $O(2^n)$ is the loose bound.

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_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] means …”. The recurrence follows from asking how 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.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading