Dynamic Programming Patterns: Finding the Recurrence

Write the recursive solution to Fibonacci and it’s three lines that read like the definition. Then call it on fib(50) and go make coffee, because fib(48) gets recomputed twice, fib(47) three times, and the redundant work balloons into millions of calls. That waste — the same subproblem solved over and over — is what dynamic programming exists to cut: solve each subproblem once, write the answer down, and an exponential recursion collapses to the number of distinct subproblems times the work each one does — often linear, sometimes $O(n^2)$ or more. The loop that does the writing-down is trivial. The part that stalled me was always the step before it — deciding what to write down and how one entry leans on the others.

So this hub is almost entirely about that one step — finding the recurrence — and then a map of the 1D DP problems by the shape of recurrence they use, so a new problem feels like one you’ve seen.

The table is just a recursion tree, flattened

That collapse from a fat recursion tree into a flat table you fill once is dynamic programming — there’s no separate machinery to learn. If the why behind it (optimal substructure, overlapping subproblems, top-down vs bottom-up) is still fuzzy, I worked through it separately in Dynamic Programming Explained. This hub assumes you buy that DP = recursion + memory and jumps to the part that actually takes practice.

The only hard part: naming dp[i]

Every 1D DP solution I’ve written came down to answering four questions in order. Rush them and you get a table that doesn’t mean anything.

1. What’s the subproblem? Define dp[i] in one precise English sentence — “the most money robbable from houses 0..i.” If you can’t say it in a sentence, you don’t have it yet.
2. How does dp[i] use earlier entries? This is the recurrence. It’s almost always a small choice: extend or restart, take or skip, the best of a few predecessors.
3. What are the base cases? The smallest inputs you can answer without the recurrence — dp[0], sometimes dp[1].
4. Where’s the answer? Usually dp[n-1] or dp[n], but sometimes it’s the max over all dp[i] — and mixing those two up is a classic off-by-one.

Here’s the whole thing on Climbing Stairs, the “Fibonacci in disguise” everyone starts with. dp[i] = the number of ways to reach step i. You get there from one step below or two below, so dp[i] = dp[i-1] + dp[i-2], with dp[0] = dp[1] = 1:

int prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; i++) {
    int cur = prev1 + prev2;   // dp[i] = dp[i-1] + dp[i-2]
    prev2 = prev1;
    prev1 = cur;
}
return prev1;

Notice there’s no array. Once you see that dp[i] only reaches back two steps, you keep two variables instead of n — the rolling trick that drops space to $O(1)$ for any recurrence whose lookback is a fixed number of steps. (Problems whose recurrence reaches across many earlier entries — Longest Increasing Subsequence and Word Break each scan every prior position — keep the full array.) House Robber reuses that exact shape — two rolling variables — but with its own bases and transition: start prev1 = prev2 = 0, walk every house, and take cur = max(prev1, prev2 + nums[i]) — skip this house, or rob it and add the best from two houses back. Same rolling structure, different recurrence; that swap is the whole skill.

The 1D DP problems, grouped by recurrence shape

NeetCode’s 1D list looks like twelve unrelated puzzles. It’s really five recurrence shapes:

• Step back one or two. Climbing Stairs, Min Cost Climbing Stairs, House Robber, House Robber II (a circle — run the line twice, once without the first house, once without the last), Decode Ways (each position depends on the last one or two digits being valid). All of them are “dp[i] from dp[i-1] and maybe dp[i-2].”
• Best run ending here. Maximum Product Subarray is the twist-heavy member — you carry both a running max and min because a negative flips them. Its simpler cousin — parked in NeetCode’s Greedy section rather than these twelve, but pure DP at heart — is Kadane’s on Maximum Subarray, the cleanest “extend or restart” decision you’ll meet.
• Best over every earlier entry. Longest Increasing Subsequence: dp[i] scans all j < i for the best sequence it can extend, which is why the naive version is $O(n^2)$ (there’s an $O(n \log n)$ version that binary-searches instead).
• Fill up to a target. Coin Change and Partition Equal Subset Sum size their table by a target — an amount, a subset sum — rather than by the input, and dp[t] asks “can I build t, or what’s the cheapest way.” Word Break is the near cousin whose index really is a prefix position, but it shares the flavor: each answer is built by asking whether some earlier split leaves a valid remainder.
• Expand around a center. Longest Palindromic Substring and Palindromic Substrings break the mold — the cheapest solution grows a palindrome outward from each center rather than filling a 1D array, though you can also write them as a table.

When a new problem lands, I don’t ask “is this DP” anymore — I ask “which of these five is it,” and the recurrence usually falls out of that.

Top-down or bottom-up?

Two ways to fill the same table. Top-down writes the natural recursion and slaps a memo (a HashMap or an array of sentinels) on it — closest to how you thought about the problem, and it only computes states you actually reach. Bottom-up loops from the base cases forward — no recursion stack, and it’s where the rolling-variable space trick lives. I reach for top-down when the recurrence is easy to state but the iteration order is fiddly, bottom-up when I want the $O(1)$ space. Both are covered in the foundations write-up.

Reading the cost off the table

DP complexity has a tidy shape: number of states × work per state. Climbing Stairs is n states doing $O(1)$ each → $O(n)$. Coin Change is amount states each scanning every coin → $O(\text{amount} \times \text{coins})$. Longest Increasing Subsequence is n states each scanning back over n → $O(n^2)$. Once the table is defined, you can read the runtime straight off its dimensions before writing a line.

Memoizing is also just caching, which is why it felt familiar coming from backend work: a memo table is a cache in front of an expensive pure function, keyed by its arguments, storing a result so you never pay for it twice. Same instinct as putting a cache ahead of a slow service — scoped down to a single recursion.

Where the work really is

If you take one thing from this: the array-filling loop is never the hard part of a DP problem, so don’t spend your interview minutes there. Spend them writing dp[i] as one honest English sentence and pinning down how it leans on earlier entries. Get that recurrence right and the code — rolling variables, base cases, a final return — writes itself.

References

• NeetCode 150 — 1D Dynamic Programming — the problem set this hub maps.
• Dynamic Programming Explained — DP as divide & conquer plus memory, memoization vs tabulation.