AntInLoop

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