Fibonacci Number
Problem Statement
The Fibonacci numbers are defined by F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n > 1. Given n, return F(n).
Input
A single integer n, the Fibonacci index to compute.
Output
An integer: the value of F(n).
Constraints
- •
0 <= n <= 30
Examples
Example 1
n = 2
1Example 2
n = 3
2Example 3
n = 4
3Learning Objectives
- Recognise the simplest two-term 1D DP recurrence.
- Translate a mathematical recurrence into an iterative bottom-up loop.
- Compress a DP table to two rolling variables when only the previous two states are needed.
Intuition
The definition already tells us the dependency graph: every Fibonacci value needs exactly the two values before it. If you try to compute it with plain recursion, the same smaller values are recomputed again and again. Dynamic programming removes that waste by building the values once, in increasing order.
For F(n), the only live information needed at step i is F(i - 2) and F(i - 1). Once F(i) is computed, the older value F(i - 2) will never be used again. That is why the full array is unnecessary: two rolling variables represent the last two DP cells.
Common mistakes
- ×Using exponential recursion even though the recurrence has overlapping subproblems.
- ×Returning **1** for **n = 0** because of a copied climbing-stairs base case.
- ×Updating the rolling variables in the wrong order and losing the old previous value.
- ×Allocating an array for every input even though each state only needs two previous values.
State Definition
Let dp[i] be the Fibonacci value F(i). The answer we want is dp[n].
State Transition
Each Fibonacci value is the sum of the two immediately previous values:
dp[i] = dp[i - 1] + dp[i - 2] for i >= 2.
Base cases anchor the sequence: dp[0] = 0 and dp[1] = 1.
Solutions
Solution: Bottom-up with two rolling variables
Because dp[i] depends only on dp[i - 1] and dp[i - 2], keep those two values and sweep forward from 2 to n.
Step-by-step
- Return n directly for n = 0 or n = 1.
- Initialise twoNumbersBack = 0 for F(0) and oneNumberBack = 1 for F(1).
- For each index from 2 through n, compute the current Fibonacci value as their sum.
- Shift the rolling window forward so the current value becomes the new previous value.
O(n)
O(1)
One loop computes each Fibonacci index once while storing only two values.
Java implementation
Dry Run
Sample input
n = 6. Track the two rolling variables as the loop computes F(2) through F(6).
| i | twoNumbersBack | oneNumberBack | current |
|---|---|---|---|
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 3 |
| 5 | 2 | 3 | 5 |
| 6 | 3 | 5 | 8 |
After index 6, oneNumberBack holds 8, so F(6) = 8.
Complexity Analysis
The rolling-variable form is the expected optimal solution: linear time and constant space.
Bottom-up with two rolling variables
O(n)
O(1)
One loop computes each Fibonacci index once while storing only two values.
Interview Tips
Use this problem to show the DP template cleanly: define a state, name the recurrence, seed the base cases, then compress space because the dependency window has size two. Be explicit that this is not the same base case as Climbing Stairs; Fibonacci starts at 0, 1, while Climbing Stairs counts ways and starts from 1, 1.
Likely follow-ups
- How would you return the whole Fibonacci sequence up to **n**?
- How would you compute **F(n)** modulo a large number?
- Can this recurrence be solved faster than O(n) using matrix exponentiation?
- How does this recurrence change when modelling Climbing Stairs?
Similar Problems
Key Takeaways
- Fibonacci is the smallest example of overlapping subproblems in 1D DP.
- The recurrence is **dp[i] = dp[i - 1] + dp[i - 2]** with base cases **0** and **1**.
- A constant dependency window can be compressed to rolling variables.