DP: Recursion With a Memory

The problem DP solves

Write the natural recursion for the Fibonacci numbers — fib(n) = fib(n-1) + fib(n-2) — and call fib(50). It never finishes in reasonable time. Why? Draw the call tree: fib(50) calls fib(49) and fib(48); fib(49) calls fib(48) again; fib(48) gets computed twice, fib(47) three times, fib(46) five times. The tree has on the order of 2^50 nodes, yet there are only 50 distinct questions being asked.

That is the signature of overlapping subproblems: the recursion keeps re-answering questions it already answered. Dynamic programming (DP) is the fix — answer each distinct subproblem once, store the answer, and reuse it. Fifty stored answers instead of 2^50 calls. DP is not a new kind of algorithm; it is recursion with a memory.

Two ways to add the memory

Top-down (memoization). Keep the recursion exactly as written, but before computing, check a cache; after computing, store. "Memoize" just means "cache the function's results".

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Bottom-up (tabulation). Skip recursion entirely: figure out the order in which answers depend on each other, then fill a table in that order with a loop.

def fib(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Both are O(n). Memoization is often easier to write (the recursion is the recurrence) and only computes states actually reached; tabulation avoids recursion-depth limits and opens the door to space optimization. Interviewers accept either — know how to convert between them.

The four-step recipe

Every 1-D DP solution answers four questions, in this order:

1. State — what does dp[i] mean, in one plain-English sentence? This is the step people skip, and it is where wrong solutions are born. "dp[i] = the number of distinct ways to reach step i." Write the sentence before any code.
2. Recurrence — how does dp[i] follow from earlier entries? This encodes the last decision: to stand on step i you arrived from step i-1 or step i-2, so dp[i] = dp[i-1] + dp[i-2].
3. Base cases — the smallest states with obvious answers: dp[0] = 1, dp[1] = 1.
4. Order and answer — fill left to right; the answer sits at dp[n].

Worked run, Climbing Stairs with n = 5:

Eight ways to climb five steps — Fibonacci in disguise.

A second family: choose or skip

House Robber: houses hold money [2, 7, 9, 3, 1]; robbing two adjacent houses trips the alarm; maximize the haul.

State: dp[i] = the most money obtainable from the first i+1 houses. Recurrence — the last decision is house i itself: skip it (keep dp[i-1]) or rob it (add its value to dp[i-2], since house i-1 is then off-limits):

dp[i] = max(dp[i - 1], dp[i - 2] + val[i])

Trace: dp = [2, 7, 11, 11, 12]. At house 2 (value 9): max(7, 2 + 9) = 11. At house 4 (value 1): max(11, 11 + 1) = 12.

The circular variant (House Robber II) has a clean reduction: house 0 and the last house are now adjacent, so they cannot both be robbed — run the linear robber twice, once excluding the first house and once excluding the last, and take the better result.

A third family: min/max cost to hit a target

Coin Change: fewest coins from [1, 3, 4] summing to 6. State: dp[a] = fewest coins making amount a. Recurrence: the last coin used was some c, so dp[a] = 1 + min(dp[a - c] for each usable c).

One trap dominates this family: initialization. "Impossible" must start as infinity, not 0 — a min() over values seeded with 0 silently claims every amount is free. Seed dp[0] = 0 (zero coins make zero) and everything else with infinity:

dp[6] = 2 (coins 3 + 3). Note that a greedy "always take the biggest coin" gives 4 + 1 + 1 = three coins — wrong. Interacting choices are why this is DP, not greedy.

Longest Increasing Subsequence: looking back at all of them

Sometimes dp[i] depends on every earlier state, not just the last two. LIS: dp[i] = length of the longest increasing subsequence ending exactly at index i. Then dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i]) — extend the best earlier subsequence whose tail is smaller. That inner scan makes it O(n²), which passes in interviews; the O(n log n) patience-sorting upgrade is a bonus, not a requirement. The answer is the max over the whole table, not dp[n-1] — the best subsequence can end anywhere.

Space optimization

When the recurrence only reaches back a fixed distance — dp[i-1] and dp[i-2] — the table is overkill. Keep two rolling variables:

prev2, prev1 = 1, 1
for i in range(2, n + 1):
    prev2, prev1 = prev1, prev1 + prev2
return prev1

O(n) space becomes O(1). Mention this even if the interviewer does not ask; it is a cheap way to show depth. (LIS cannot roll — it reaches arbitrarily far back.)

Recognition signals

Reach for 1-D DP when you see: "how many ways to reach/build/decode…", "minimum or maximum cost over a sequence of decisions", "can this string be segmented", "longest … subsequence". Confirm with two checks: the naive recursion recomputes identical subproblems, and n is far too large for backtracking's exponential enumeration (n up to 10^5 says DP; n up to 20 says backtracking may be intended).

One last habit: watch string-position edge cases. Decode Ways is a two-step recurrence like Climbing Stairs, but the character '0' can kill the one-digit option ("06" decodes to nothing) — the recurrence must guard each transition's validity, not just add blindly.