Fibonacci Sequence & Intro to Dynamic Programming
The Fibonacci Sequence introduces Dynamic Programming through overlapping subproblems, showing the progression from O(2^n) recursion to O(n) memoization, O(1)-space tabulation, and O(log n) matrix exponentiation.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Fibonacci Sequence & Intro to Dynamic Programming
The Fibonacci Sequence ($F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$) is the canonical gateway into Dynamic Programming (DP). Naive recursion recomputes the same subproblems exponentially many times ($O(2^n)$), whereas caching results (memoization) or building bottom-up (tabulation) drops the runtime to $O(n)$—and rolling two variables reduces memory to $O(1)$!
At a Glance
| Approach | Time | Auxiliary Space |
| :--- | :--- | :--- |
| Naive Recursion | $O(2^n)$ | $O(n)$ call stack |
| Top-Down Memoization | $O(n)$ | $O(n)$ |
| Bottom-Up Tabulation (Rolling) | $O(n)$ | $O(1)$ |
| Matrix Exponentiation | $O(\log n)$ | $O(1)$ |
---
How It Works (Bottom-Up Rolling DP)
1. Handle base cases: if $n \le 1$, return $n$.
2. Track only the last two values: prev2 = 0 ($F_0$) and prev1 = 1 ($F_1$).
3. For i = 2 to n:
cur = prev1 + prev2- Shift:
prev2 = prev1,prev1 = cur.
4. Return prev1.
procedure fib(n):
if n <= 1: return n
prev2 = 0, prev1 = 1
for i = 2 to n:
cur = prev1 + prev2
prev2 = prev1
prev1 = cur
return prev1
Step-by-Step Trace ($n = 6$)
| i | prev2 | prev1 | cur = prev1 + prev2 |
| :---: | :---: | :---: | :---: |
| Init | 0 | 1 | — |
| 2 | 1 | 1 | 1 |
| 3 | 1 | 2 | 2 |
| 4 | 2 | 3 | 3 |
| 5 | 3 | 5 | 5 |
| 6 | 5 | 8 | 8 |
---
Complexity & Key Insights
- Two Ingredients of DP: (1) Overlapping subproblems ($F_3$ is computed multiple times in $F_5 = F_4 + F_3$ and $F_4 = F_3 + F_2$), and (2) Optimal substructure / recurrence ($F_n$ depends solely on smaller subproblems).
- Space Optimization Pattern: Whenever
dp[i]only depends on the last $k$ states (dp[i-1],dp[i-2]), replace the $O(n)$ array with $k$ scalar variables for $O(1)$ space. - Matrix Exponentiation ($O(\log n)$): Writing $\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$ computes $F_n \bmod 10^9+7$ even for $n = 10^{18}$ using Fast Exponentiation!
---
Practice Problems
Easy
1. $n$-th Fibonacci Number in $O(1)$ Space
Compute $F_n$ for $0 \le n \le 90$ using 64-bit integers and $O(1)$ space.
Approach: Rolling two-variable tabulation. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
long long fib(int n) {
if (n <= 1) return n;
long long prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; ++i) {
long long cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int main() {
std::cout << fib(10) << " " << fib(50) << "\n";
return 0;
}
</details>
2. Climbing Stairs (LeetCode 70)
You are climbing a staircase of $n$ steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach step $n$?
Approach: Reaching step i comes either from i - 1 (1-step) or i - 2 (2-step), so ways[i] = ways[i - 1] + ways[i - 2] with ways[0] = 1, ways[1] = 1. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
long long climbStairs(int n) {
if (n <= 1) return 1;
long long prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; ++i) {
long long cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int main() {
std::cout << climbStairs(5) << " " << climbStairs(10) << "\n";
return 0;
}
</details>
---
Intermediate
3. House Robber (LeetCode 198)
Given non-negative cash amounts nums[i] along a street, find the maximum amount you can rob without robbing two adjacent houses.
Approach: At house i, either skip it (dp[i - 1]) or rob it (dp[i - 2] + nums[i]): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]). Compress to two rolling variables. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int rob(const std::vector<int>& nums) {
int prev2 = 0, prev1 = 0;
for (int x : nums) {
int cur = std::max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int main() {
std::cout << rob({2, 7, 9, 3, 1}) << "\n"; // 12
return 0;
}
</details>
4. Decode Ways (LeetCode 91)
A message of digits ('1'–'26' mapped to 'A'–'Z') is given. Count the number of ways to decode it.
Approach: dp[i] is the number of ways to decode the prefix of length i. Add dp[i - 1] if s[i - 1] != '0', and add dp[i - 2] if the 2-digit number s[i - 2..i - 1] lies in [10, 26]. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <string>
int numDecodings(const std::string& s) {
if (s.empty() || s[0] == '0') return 0;
int prev2 = 1, prev1 = 1;
for (size_t i = 1; i < s.size(); ++i) {
int cur = 0;
if (s[i] != '0') cur += prev1;
int twoDigit = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (twoDigit >= 10 && twoDigit <= 26) cur += prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int main() {
std::cout << numDecodings("226") << " " << numDecodings("06") << "\n"; // 3 0
return 0;
}
</details>
---
Hard
5. $F_n \bmod (10^9 + 7)$ for $n \le 10^{18}$ (Matrix Exponentiation)
Compute the $n$-th Fibonacci number modulo $10^9 + 7$ for huge $n$ (up to $10^{18}$).
Approach: Raise the $2 \times 2$ transition matrix $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ to the $n$-th power via binary exponentiation. Time: $O(\log n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <array>
#include <iostream>
constexpr long long MOD = 1'000'000'007LL;
using Mat2 = std::array<std::array<long long, 2>, 2>;
Mat2 mul(const Mat2& A, const Mat2& B) {
Mat2 C{{{0, 0}, {0, 0}}};
for (int i = 0; i < 2; ++i)
for (int k = 0; k < 2; ++k)
for (int j = 0; j < 2; ++j)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
long long fibMod(long long n) {
if (n == 0) return 0;
Mat2 res{{{1, 0}, {0, 1}}};
Mat2 base{{{1, 1}, {1, 0}}};
while (n > 0) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][1];
}
int main() {
std::cout << fibMod(10) << " " << fibMod(1000000000000LL) << "\n";
return 0;
}
</details>
---
Related Algorithms
- Coin Change — next step in 1D DP with variable transitions.
- Fast Exponentiation — powers $O(\log n)$ matrix exponentiation.