Fibonacci DP

The simplest DP family: each answer depends on a fixed handful of earlier answers, so a loop and two or three variables solve it in O(n) time and O(1) space.

Overview

The shape of the recurrence

The Fibonacci numbers start 0, 1 and each next number is the sum of the two before it: F(n) = F(n−1) + F(n−2). Many problems have the same shape. The answer at position i depends only on the answers at a few positions just before it, and nothing else. That shape is what this topic calls Fibonacci DP.

Fibonacci — The i-th number — dp[i-1] + dp[i-2] — sum
Climbing Stairs — Ways to reach step i — dp[i-1] + dp[i-2] — sum
Tribonacci — The i-th number — dp[i-1] + dp[i-2] + dp[i-3] — sum
Min Cost Climbing Stairs — Cheapest way to stand on step i — min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) — min
House Robber — Most money from houses 0 to i — max(dp[i-1], dp[i-2] + value[i]) — max
Decode Ways — Ways to decode the first i digits — dp[i-1] if the digit is valid, plus dp[i-2] if the pair is valid — sum with conditions

The combine step changes (sum, min or max) but the plan never does: base cases, then a loop from left to right.

Why plain recursion is too slow

Writing the recurrence as a recursive function repeats work. To compute F(5), the function computes F(3) twice and F(2) three times.

The call count grows about as fast as the Fibonacci numbers themselves.

5 — 15 — 4
10 — 177 — 9
20 — 21,891 — 19
25 — 242,785 — 24

From an array to two variables

The bottom-up version fills dp[0], dp[1], dp[2], ... in order. Each new cell reads only the two cells before it, so the array is not needed. Keep the last two values in two variables and slide them forward.

A trace of Climbing Stairs for n = 5, where dp[i] is the number of ways to reach step i using steps of 1 or 2.

2 — 1 — 1 — 2
3 — 1 — 2 — 3
4 — 2 — 3 — 5
5 — 3 — 5 — 8

The answer is 8. Time O(n), space O(1). Make this cut for every problem in the family.

Include or exclude: House Robber

Not every recurrence is a sum. In House Robber each house holds money, you cannot rob two neighbors, and you want the most money. At house i you either skip it (keep dp[i-1]) or rob it (dp[i-2] plus its value).

0 — 2 — 0 — 0 + 2 = 2 — 2
1 — 7 — 2 — 0 + 7 = 7 — 7
2 — 9 — 7 — 2 + 9 = 11 — 11
3 — 3 — 11 — 7 + 3 = 10 — 11
4 — 1 — 11 — 11 + 1 = 12 — 12

The answer is 12 (houses 0, 2 and 4). The loop is the same as Fibonacci with max in place of plus.

When the houses form a circle (House Robber II), the first and last house are neighbors. Run the linear version twice, once without the first house and once without the last, and take the larger result.

Base cases decide counting problems

For 'number of ways' problems the base case is dp[0] = 1: there is exactly one way to do nothing. Setting it to 0 makes every later count 0. For 'minimum cost' problems the base is 0 cost, and for 'maximum value' problems it is 0 value. The table below shows how a wrong base case spreads.

1 — 1 — 2 — 3 — 5 — right
0 — 1 — 1 — 2 — 3 — wrong: every value is one Fibonacci number behind

Huge n: matrix power

When n is around 10¹⁸, a loop of n steps is too slow. The step from (F(n), F(n−1)) to (F(n+1), F(n)) is a fixed 2 by 2 matrix multiplication, so F(n) is that matrix raised to the power n, and repeated squaring computes a power in O(log n) multiplications. The answer is usually asked modulo a prime, because F(10¹⁸) itself has about 2 × 10¹⁷ digits and cannot be stored.

Loop with two variables — O(n) — n up to about 10⁷
Matrix power by repeated squaring — O(log n) — n up to 10¹⁸, with a modulus

What you will be able to do

Recognize a Fibonacci-shaped recurrence from the words 'ways', 'cost' or 'rob' and a linear input.
Write the loop with the right base cases and the right combine step (sum, min or max).
Cut the space to O(1) and explain why it is safe.
Handle the circular variant by running the linear version twice.
Explain matrix power for huge n without being asked to code it.

When to use it

The question counts the ways to reach a target with a few fixed step sizes
The question asks for the cheapest or most valuable way through a line of positions
Each position offers a choice (take or skip, step 1 or 2) that only depends on the last one or two positions
The recurrence reads dp[i-1], dp[i-2], ... up to some small fixed k
A plain recursive solution repeats the same calls and times out

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio