“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Etude: Fibonacci and the DP family

Etudes

Fibonacci is the first dynamic-programming problem anyone learns, which is funny because it's barely a dynamic-programming problem at all. It's just a recurrence. There's no decision to make, no optimization to do — you take two numbers, add them, and write the answer down. The reason it gets billed as DP is that the memoization habit Fibonacci teaches (don't recompute subproblems) is the entry point to a whole family of harder problems where memoization is the difference between exponential and polynomial time.

This page walks the family. Each member is one small modification away from the previous one — add a max(), extend the lookback window, gate the terms with an if-statement — and by the end you've reached Coin Change, which is what everyone agrees is "a real DP problem." Watching the code morph step by step is the point. Fibonacci is a bicycle; Coin Change is a Lamborghini; this page is the parts catalog that shows you how one becomes the other.

The seed: Fibonacci

The naive recursive Fibonacci is the famous bad example:

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

Exponential time, roughly O(φⁿ), because fib(5) calls fib(4) and fib(3), then fib(4) recomputes fib(3) from scratch, and the wasted work compounds all the way down. The DP fix is to write each subproblem into a table and never compute it twice:

def fib(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]
    return dp[n]

That's the seed. O(n) time, O(n) space (collapsible to O(1) with two rolling variables, but we'll keep the table because the morphing variants will need it). Now look at how little has to change to get all the other problems.

The family, morphing

Step through the variants with the arrows. Highlighted lines are what changed from the previous variant. The "why" panel below the code says what the change unlocks.

1 / 8

Fibonacci (the seed)

starting point

 def fib(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]
     return dp[n]

Two-term lookback. No choice. The recurrence sums; that's it.

By the end of that ladder you have, in your hands, the full standard-issue DP toolkit: memoization, optimization via max/min, per-element data, variable-length lookback, conditional contributions, and an inner sweep over choices. None of these showed up all at once. Each is one small mutation on the previous variant. That's the étude payoff — you didn't learn DP by studying DP, you learned it by mutating Fibonacci eight times.

Variation 1 — Climbing Stairs (Fibonacci, renamed)

You're at the bottom of a staircase with n steps. Each move climbs 1 or 2 steps. How many distinct ways can you reach the top?

The number of ways to reach step i is (ways to reach i-1, then take a 1-step) plus (ways to reach i-2, then take a 2-step). That's literally Fibonacci's recurrence. The only difference: there is one way to "be at the bottom" (do nothing) and one way to be on step 1 (take a single 1-step), so the base cases are both 1 instead of Fibonacci's 0 and 1.

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

print(climb(5))   # 8
print(climb(10))  # 89

Climbing Stairs is what proves Fibonacci wasn't really about rabbits — it was about any counting problem where the state at step n is determined by the previous two states. The recurrence is the same; only the interpretation changes.

Variation 2 — Tribonacci (window of 3)

Same flavor, but each term is the sum of the previous three. The Fibonacci recurrence assumed lookback 2; Tribonacci shows that the 2 wasn't sacred. You can look back however far you want, as long as you seed enough base cases.

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

print(trib(10))  # 81

Notice the loop now starts at i = 3, not 2 — you have to wait until you've seeded three values before the recurrence is well-defined. That's a small bug-magnet in extended-lookback DP: forgetting that dp[i-3] needs i ≥ 3, not i ≥ 2. By Coin Change the lookback range will be data-dependent, and an if c <= i guard will replace the loop offset. Tribonacci is where you start budgeting for that.

Variation 3 — House Robber (the first choice)

You're a polite home invader walking down a street of houses with nums[i] dollars in each. You can't rob two adjacent houses (alarms). Maximize loot.

At house i you face a real decision: take it (which forces skipping i-1, so you build on dp[i-2]) or skip it (and inherit dp[i-1]). The recurrence is the maximum of those two options:

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

print(rob([2, 7, 9, 3, 1]))   # 12  (rob houses 0, 2, 4)
print(rob([1, 2, 3, 1]))      # 4   (rob houses 0 and 2)

The structural jump from Fibonacci is real but small. The recurrence still looks back exactly two steps. What's new is the max(), and the per-element value nums[i-1] baked into the "take it" branch. If you delete the max() and the nums[], you are back to Fibonacci.

This is the moment when DP starts to feel like its name. The "programming" in dynamic programming is Bellman-era jargon for "tabulating decisions over stages." House Robber is the first member of the family where there's an actual decision at each stage.

Variation 4 — Min Cost Climbing Stairs

The structural mirror of House Robber: minimize a cost instead of maximizing a value. Each step i has a cost cost[i] to leave. You can start at step 0 or step 1. Reach the top (one past the last step) with minimum total cost.

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

print(min_cost([10, 15, 20]))                  # 15
print(min_cost([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6

If you understood House Robber, you understood this one for free. The only conceptual move is "max → min." That's deliberate — the family is teaching you that the optimization direction is a knob you turn, not a fundamental difference. Future you, facing a fresh DP problem, will read the requirement (max profit? min steps? count of ways?) and auto-select between max, min, and sum.

Variation 5 — Maximum Subarray (Kadane's algorithm)

Given an array of integers (possibly negative), find the contiguous subarray with the largest sum. Kadane is the famous one-pass DP.

The DP state is "best subarray sum ending exactly at index i". At each step the choice is: extend the previous best subarray (add nums[i] to dp[i-1]) or start a new one at i (nums[i] alone). Whichever is bigger.

def max_subarray(nums):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
    return max(dp)

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6  (subarray [4, -1, 2, 1])
print(max_subarray([-3, -1, -2]))                      # -1

Two things to notice. First, the lookback is one step now, not two — you only need dp[i-1]. Second, the answer is max(dp), not dp[-1]. The best subarray can end anywhere; we look at the whole table and take the maximum. This is the first member of the family where the answer isn't at the end of the table — a small move, but characteristic of DP-as-a-genre.

Variation 6 — Decode Ways (conditional contributions)

A string of digits like "226" can be decoded as letters (A=1, ..., Z=26). How many decodings are there? "226" → "BBF", "BV", "VF" → 3.

The recurrence is still dp[i] = dp[i-1] + dp[i-2], a Fibonacci sum, but each term is gated by a validity check. Add dp[i-1] only if the single-digit s[i-1] is in [1, 9]; add dp[i-2] only if the two-digit window s[i-2:i] is in [10, 26]. The structural pattern is "sum over the legal predecessors."

def decode(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 0 if s[0] == '0' else 1
    for i in range(2, n + 1):
        one = int(s[i - 1])
        two = int(s[i - 2:i])
        if 1 <= one <= 9:
            dp[i] += dp[i - 1]
        if 10 <= two <= 26:
            dp[i] += dp[i - 2]
    return dp[n]

print(decode("226"))   # 3
print(decode("12"))    # 2
print(decode("06"))    # 0

House Robber gated by choice (which option is bigger?). Decode Ways gates by validity (is this predecessor legal?). These two flavors of gating — choose-the-best vs include-if-allowed — cover most of what you'll see in interview-grade DP.

Variation 7 — Coin Change (the Lamborghini)

Given coin denominations like [1, 2, 5] and a target amount, return the minimum number of coins that sum to the target (or -1 if impossible).

The lookback set is no longer a fixed window of 2 or 3 or "everything that fits" — it's the coin denominations, which can be anything. For each amount i we sweep every coin c that fits, look at dp[i - c], and ask "would using one of these coins on top of dp[i - c] beat the current dp[i]?"

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 2, 5], 11))   # 3   (5 + 5 + 1)
print(coin_change([2], 3))          # -1
print(coin_change([1], 0))          # 0

Coin Change is the synthesis. You can read every feature off the code by pointing at the ancestor that introduced it:

Memoized table (dp[]): from Fibonacci.
Optimization step (min()): from Min Cost Climbing Stairs (which got it from House Robber's max()).
Per-step cost (+ 1 for using a coin): from Min Cost Climbing Stairs.
Variable-length lookback (over coins): from Tribonacci, taken to its logical conclusion — the lookback is now data-dependent, not even a fixed window.
Inner sweep over choices (for c in coins): genuinely new, but a one-line generalization of "look at i-1 and i-2" — the inner loop is what House Robber's two-option max becomes when there are k options instead of 2.
Sentinel value (float('inf')): a small but real DP move — "this state isn't reachable yet," so don't pick it as the min.

Every one of those ideas you'd already met by Variation 6. Coin Change just bolts them together. If Fibonacci-as-DP is a bicycle and Coin Change is the Lamborghini, the family in between is the parts catalog: gears, brakes, drivetrain, fuel-injection, suspension. Each variation hands you one part and shows you what it does in isolation. By the time you reach the Lamborghini, you've already installed every component by hand.

What the family is teaching you

The reason this family is worth working as an étude rather than learning each problem fresh is the meta-skill: when you see a new problem, you ask which axis is this varying? Is the recurrence longer? Is there a choice? Is the choice gated? Is the lookback set arbitrary? Is the state higher-dimensional? Once you've internalized the axes, classifying a new DP problem stops being mystery work and becomes feature-matching.

The other thing — and this one is worth saying out loud, because most DP courses bury it — Fibonacci is genuinely a poor exemplar of dynamic programming by itself, because it has no decision step. The pedagogical magic isn't that Fibonacci is DP; it's that Fibonacci is the seed of a family in which each member adds exactly one DP feature. The family is the lesson. Fibonacci alone is just the bicycle.