Fibonacci Sequence --
DP & Memoization

The Fibonacci sequence is one of the most famous examples used to introduce dynamic programming and memoization.

A naive recursive solution repeatedly recalculates the same values, leading to exponential time complexity. Using memoization, previously computed results are stored and reused, dramatically improving performance.

1. Introduction

The Fibonacci sequence is one of the most famous examples used to introduce dynamic programming and memoization. In this lesson, we will compare the naive recursive solution with the optimized memoized approach and understand why caching previously computed results dramatically improves performance.

The Fibonacci sequence is a mathematical sequence of numbers in which each next number is obtained as the sum of the previous two. The sequence starts with 0 and 1 and continues infinitely. The first ten elements look like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

The length of the sequence depends on which element n we want to compute. For example, if we want to calculate F(7), this means we are considering the first 8 elements of the sequence (indexed from 0 to 7):
n = 7 → the sequence has 8 elements (from F(0) to F(7)).

This gives an intuitive understanding before moving on to dynamic programming: the larger the value of n, the more computations are required — especially when using naive recursion. This clearly demonstrates how computational complexity can be reduced by switching from plain recursion to memoization or tabulation. In this lesson, we present three approaches:

• Top-down (recursion + memoization)
• Bottom-up (tabulation)
• Performance comparison

2. Definition of the Fibonacci Sequence

When we want to formally describe the Fibonacci sequence, we introduce a function F(n) which returns the n-th Fibonacci number for each natural (or integer) value of n. Introducing the function F allows us to precisely express the relationship between different elements of the sequence — Fibonacci numbers are not independent; each new number is determined by a combination of previous ones. In other words, instead of describing the sequence in words, the function F(n) provides a mathematically clear and concise way to define the rules that generate the entire sequence.

This function is defined recursively: the base cases determine the beginning of the sequence, and each subsequent value is obtained by summing the two preceding values. This leads to the following simple, yet very powerful definition:

F(0) = 0  
F(1) = 1  
F(n) = F(n − 1) + F(n − 2)

For a basic explanation of the Fibonacci sequence and a simple recursive implementation, see the introductory lesson:
Fibonacci Sequence — Introduction

3. Naive Recursion (for Comparison)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
  

This approach has exponential time complexity O(2ⁿ), which makes it very inefficient for larger values of n.

The same subproblems are recomputed many times, which leads to unnecessary overhead.

4. DP Top-down: Recursion + Memoization

The top-down approach (recursion + memoization) starts from the final problem — computing F(n) — and recursively breaks it down into smaller subproblems (F(n−1), F(n−2), ...).

However, unlike naive recursion which repeats the same computations, the top-down approach stores the results of subproblems in a separate table (memo).

When the same subproblem is requested again, the value is returned immediately from the table, without making another recursive call.

This approach is intuitive because it closely follows the mathematical definition of the Fibonacci function, while reducing the time complexity from exponential to linear.

#include <iostream>
#include <vector>
using namespace std;

// Memo table that stores previously computed values.
// We use long long because Fibonacci numbers grow very quickly.
vector<long long> memo;

// Recursive function with memoization
long long fib_memo(int n) {

    // Base cases: F(0) = 0, F(1) = 1
    if (n <= 1)
        return n;

    // If the value has already been computed, return it immediately.
    if (memo[n] != -1)
        return memo[n];

    // Otherwise, compute it recursively and store the result.
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);

    // Return the stored value.
    return memo[n];
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;

    // Initialize the memo array of size n+1, all values set to -1.
    // -1 means the value has not been computed yet.
    memo.assign(n + 1, -1);

    cout << "Fibonacci (Top-down) = " << fib_memo(n) << endl;
}
  

Advantages

• Fast computation — O(n)
• Natural recursive logic

Disadvantages

• Recursive calls increase stack memory usage

Edge Cases and Important Limitations

Although memoization significantly speeds up Fibonacci computation, it is important to handle edge cases correctly and understand implementation limitations.

1. Edge Cases

• n = 0
  The function should return 0. This is a valid value and part of the standard Fibonacci definition.
• n = 1
  The function should return 1. This is usually treated as a base case.
• n < 0
  Negative Fibonacci indices do not make sense in the standard definition. Recommendations:
  • throw an error / exception
  • or explicitly document that the function is defined only for n ≥ 0

2. n Size Limitations (Memory and Time)

Top-down memoization uses recursion and a memo table of size O(n). This means: if n is very large, memory and stack depth become a concern.

• n ≈ 10⁶: memo table uses about 8 MB (if using long long), recursion may cause stack overflow.
• n ≈ 10⁷: memo table requires ~80 MB → very likely MLE (Memory Limit Exceeded). Recursion depth of 10⁷ is practically impossible → certain stack overflow.
• n > 10⁷: top-down approach is not feasible. Alternative methods are needed (see below).

3. Potential long long Overflow

The long long type (64-bit) can hold values up to approximately 9.2 × 10¹⁸. This means:

• F(92) is the largest Fibonacci number that fits in a long long.
• F(93) and beyond exceed the range → overflow occurs.

If you work with n > 92, the result will definitely not fit in a 64-bit type.

4. What to Use for Very Large n?

If you need to compute F(n) for very large n like 10⁷, 10⁸, 10⁹ or even larger, memoization is not suitable. Instead, more efficient and stable methods are used:

• Matrix exponentiation: O(log n) time, constant memory. Uses a 2×2 matrix and fast exponentiation.
• Fast exponentiation using the golden ratio (Binet formula) — not recommended due to precision loss for large n.
• Modular Fibonacci (when result is required modulo some number, e.g., 10⁹+7).
• BigInteger / arbitrary precision (automatic in Python, in C++ via libraries): allows computing F(n) for hundreds of thousands or millions.
• Fast Doubling algorithm: the fastest and most precise approach for large n. Works in O(log n) time and avoids deep recursion.

In short: memoization is good for medium n (up to ~10⁵), but not for extremely large n.

Illustration: Number of Calls and Recursion Depth — Naive Recursion vs. Memoization

This interactive block shows, for a given n, how many function calls naive recursion (without DP) makes, and how many calls the memoized version requires. It also displays the maximum recursion depth (stack depth). For small n, you can also see the call tree structure.

Brief Explanation (for Teachers)

• Naive Recursion: the number of calls satisfies the relation C(0)=1, C(1)=1, C(n)=1 + C(n-1) + C(n-2) if we count the initial call. It grows ≈ φ^n.
• Memoized (Top-down): each index 0..n is computed at most once → number of calls ≈ n+1 (for Fibonacci), and stack depth ≤ n.
• This difference explains why memoization reduces time from exponential to linear.

5. DP Bottom-up: Tabulation

The bottom-up approach (tabulation) means that we build solutions to subproblems iteratively from the smallest to the largest. For the Fibonacci sequence, this means first computing F(0) and F(1), then F(2), F(3), and so on up to F(n). This approach does not use recursion but directly fills the DP array (table) in order, avoiding deep recursive calls.

Advantages of the bottom-up approach:

• No recursion → no risk of stack overflow.
• Time complexity is linear O(n).
• Clear iterative logic → often easier to debug and understand than top-down recursion.

#include <iostream>
#include <vector>
using namespace std;

long long fib_tab(int n) {
    if (n <= 1) return n;

    vector dp(n + 1);  // DP array to store F(0)..F(n)
    dp[0] = 0;                     // base case
    dp[1] = 1;                     // base case

    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];  // DP transition: F(i) = F(i-1) + F(i-2)

    return dp[n];  // return the requested Fibonacci number
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;

    cout << "Fibonacci (Bottom-up) = " << fib_tab(n) << endl;
}

Advantages

• No recursion
• O(n) time

Disadvantages

• Uses O(n) extra memory

6. Optimal Bottom-up Version (O(1) Memory)

long long fib_opt(int n) {
    if (n <= 1) return n;

    long long a = 0, b = 1;  // store only the previous two numbers

    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;  // return F(n)
}

Advantages

• O(1) memory
• Most efficient approach for large n

Visual Table for Bottom-up Tabulation

The table below shows how the DP array is filled during bottom-up computation of Fibonacci numbers. This helps visually understand how the algorithm gradually builds solutions for smaller subproblems.

Explanation

• Each row represents the state after one iteration of the loop.
• The blue cell indicates the index that was just computed in that iteration.
• All other cells show values already computed.
• This type of visual representation helps learners grasp the key idea of dynamic programming: we build solutions for larger indices using already solved smaller subproblems.

Alternative Solutions: DP is Not the Only Optimization

Although memoization significantly speeds up Fibonacci computation, there are other, even more efficient solutions. It is important for learners to understand that dynamic programming is not the only way to accelerate recursion.

1. Iterative Bottom-up Solution Using Only 2 Variables

This is the simplest and most efficient variant of the DP approach. Instead of an array or table, we store only the last two elements:

long long fib(int n) {
    if (n <= 1) return n;

    long long a = 0;  // F(n-2)
    long long b = 1;  // F(n-1)

    for (int i = 2; i <= n; i++) {
        long long c = a + b;  // F(n)
        a = b;
        b = c;
    }

    return b;
}

Complexity: O(n) time, O(1) memory. This is practically the best solution for most school and competitive programming tasks.

This solution falls under bottom-up DP because it uses previously computed subproblem values, but it stores only the last two numbers to optimize memory. Thus, the dynamic programming principle remains, even though space usage is reduced to O(1).

2. Matrix Exponentiation – O(log n) Solution

The Fibonacci sequence can be represented using a transformation matrix:

| F(n+1) |   =   | 1 1 | × | F(n)   |
| F(n)   |       | 1 0 |   | F(n-1) |

Thus: F(n) = (M^n)[1][0] where M is the basic Fibonacci matrix. Using **binary exponentiation (fast matrix exponentiation)**, the time complexity becomes O(log n).

This method is useful for very large n (e.g., 10¹⁵) with modular arithmetic.

2a. Matrix Exponentiation – C++ Implementation

The following code shows how the Fibonacci sequence can be computed using a 2×2 matrix and fast exponentiation (binary exponentiation). The time complexity is O(log n).

#include <iostream>
#include <vector>
using namespace std;

// Multiply two 2x2 matrices
void multiply(long long a[2][2], long long b[2][2]) {
    long long x = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    long long y = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    long long z = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    long long w = a[1][0]*b[0][1] + a[1][1]*b[1][1];

    a[0][0] = x;
    a[0][1] = y;
    a[1][0] = z;
    a[1][1] = w;
}

// Fast matrix exponentiation
void power(long long mat[2][2], long long n) {
    if(n <= 1) return;

    long long base[2][2] = {{1,1},{1,0}};
    power(mat, n/2);
    multiply(mat, mat);

    if(n % 2 != 0) multiply(mat, base);
}

// Fibonacci function using matrix
long long fib_matrix(long long n) {
    if(n == 0) return 0;
    long long mat[2][2] = {{1,1},{1,0}};
    power(mat, n-1);
    return mat[0][0];
}

int main() {
    long long n;
    cout << "Enter n: ";
    cin >> n;

    cout << "Fibonacci (matrix) = " << fib_matrix(n) << endl;
}
  

Explanation: - The matrix [[1,1],[1,0]] is used for transforming the Fibonacci sequence. - The power function recursively squares the matrix to compute mat^n. - This method allows calculating very large F(n) without deep recursion or large memory usage.

3. Fast Doubling — The Most Efficient Method for Fibonacci

Fast Doubling uses the identities:

F(2k)   = F(k) × [2F(k+1) – F(k)]
F(2k+1) = F(k+1)² + F(k)²

This recursion also works in O(log n) time, but is often faster and simpler than matrices. It is used in most serious competitive programming solutions.

// Fast doubling (returns a pair: F(n), F(n+1))
pair fib_fast(long long n) {
    if (n == 0) return {0, 1};

    auto p = fib_fast(n / 2);
    long long a = p.first;      // F(k)
    long long b = p.second;     // F(k+1)

    long long c = a * (2*b - a);        // F(2k)
    long long d = a*a + b*b;            // F(2k+1)

    if (n % 2 == 0) return {c, d};
    else return {d, c + d};
}

This method is recommended for very large n or when computation modulo some number is required.

When to Use Which Method?

• Memoization / DP: good for learning, visualization, and medium values of n
• Iterative O(1) solution: best for classic school exercises
• Matrix exponentiation: suitable for very large n and modular arithmetic
• Fast Doubling: the fastest and cleanest competitive programming solution for large n

The point is that there are faster methods than DP, and learners should be introduced to a broader range of algorithms.

7. Method Comparison

8. Conclusion

Dynamic programming dramatically improves the efficiency of computing Fibonacci numbers. The top-down approach is easy to understand, while bottom-up (especially O(1)) is the most efficient practical implementation.

Hidden Mini Quiz — Fibonacci Sequence and Memoization

Click to test your knowledge of the Fibonacci sequence, memoization, bottom-up DP and Fibonacci optimizations.

Fibonacci with Memoization — Practice Problem

To better understand the practical use of memoization and dynamic programming, the following task shows a situation where Fibonacci is not just used as a sequence, but as a part of an algorithm that solves a concrete problem.

Task: Number of Ways to Climb Stairs

An athlete wants to climb a staircase with N steps. In one move, they can take:

• 1 step, or
• 2 steps.

Calculate how many different ways the athlete can reach the top of the staircase.

Example:
If N = 4, the athlete can reach the top in the following ways:

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2

Total: 5 different ways.

Solution Idea (Guidance — No Code)

This problem is a classic example where the Fibonacci sequence appears as a consequence of the subproblem structure. Think of it this way:

• To reach step N, the athlete's last move could have been:
  • from step N - 1 (took 1 step), or
  • from step N - 2 (took 2 steps).

Therefore, the number of ways to reach step N is the sum of:

ways(N) = ways(N - 1) + ways(N - 2)

This is the same recurrence as the Fibonacci sequence, just with slightly different initial values:

• ways(0) = 1 (one way: do nothing)
• ways(1) = 1 (one step)

How to Solve the Problem Efficiently?

Direct recursion would be slow, because the same subproblem would be computed multiple times. Therefore, memoization should be used:

• Create an array or map to store already computed results.
• If the result for N is already computed → return it immediately.
• Otherwise, compute it recursively and store it in the memo table.

Try to implement a memoized recursion (top-down) for this problem on your own. The solution should be fast even for N = 40 or larger.

Fibonacci with Memoization — Problem and Solution

Task: Number of Ways to Climb Stairs. An athlete wants to climb a staircase with N steps. In one move, they can take 1 or 2 steps. Calculate how many different ways they can reach the top.

Example: If N = 4 — output is 5.

Show / Hide InstructionsShow / Hide Solution

// Number of ways to climb stairs — top-down (memoization)
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

vector<ll> memo;

// returns number of ways to climb k steps
ll ways(int k) {
    if (k <= 1) return 1;          // ways(0) = 1, ways(1) = 1
    if (memo[k] != -1) return memo[k];   // return if already computed
    // memoized calls instead of repeated recursion
    memo[k] = ways(k - 1) + ways(k - 2);
    return memo[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    // use long long for safe range; initialize memo with -1
    memo.assign(N + 1, -1);

    cout << ways(N) << '\n';
    return 0;
}
    

// Bottom-up (tabulation) + O(1) memory
#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    if (N == 0) { cout << 1 << '\n'; return 0; }
    if (N == 1) { cout << 1 << '\n'; return 0; }

    ll a = 1; // ways(0)
    ll b = 1; // ways(1)
    for (int i = 2; i <= N; ++i) {
        ll c = a + b; // ways(i) = ways(i-1) + ways(i-2)
        a = b;
        b = c;
    }
    cout << b << '\n';
    return 0;
}
    

Input:
4

Output:
5
    

Second Practice Problem — Jumping on Numbers

This task further practices understanding of recurrence relations and the use of memoization or tabulation for problems with overlapping subproblems. Although simple, it closely resembles problems from programming contests.

Problem: Jump to the Goal

You are given a single line of numbers (an array) of length N, where each element represents the maximum number of positions you can jump forward from that position.

You start at position 0 (the first element of the array), and the goal is to reach position N - 1 (the last element).

Task:
Calculate how many different ways there are to reach the last position.

Example:

Input:
N = 4
array = [1, 2, 1, 1]

Explanation:
- from position 0 you can jump at most 1
- from position 1 you can jump at most 2
- from position 2 you can jump at most 1
- from position 3 you can jump at most 1

Possible paths:
0 → 1 → 2 → 3
0 → 1 → 3

Total: 2 ways.

Solution Idea (Instructions — no code)

Consider the problem as a directed graph: from each position i you can jump to positions i+1, i+2, ..., i + a[i] (as long as you stay within array bounds).

Define the function:

ways(i) = number of ways to reach the end from position i

Then the recurrence relation is:

ways(i) = ways(i+1) + ways(i+2) + ... + ways(i + a[i])

The base case is clear:

• ways(N - 1) = 1 — you are already at the end, so there is exactly one way

How to Solve Efficiently?

This problem has overlapping subproblems: the function ways(i) would be called multiple times if you use plain recursion.

Therefore, use:

• Memoization (top-down): before each recursive call, check if the result has already been computed.
• Tabulation (bottom-up): fill the DP array from the end towards the beginning.

Note that the result can grow quickly — use long long if needed.

It is recommended to first implement the top-down version, as it is more intuitive, and then move to a bottom-up solution as a dynamic programming exercise.

Solution — Jumping on Numbers (DP with Memoization)

This section contains the full instructions and a complete solution for the problem "Jump to the Goal". The idea is to deepen understanding of recurrence relations, memoization, and tabulation, which are fundamental dynamic programming techniques.

Show / Hide InstructionsShow / Hide Solution

i + 1, i + 2, ..., i + a[i]

ways(i) = number of ways to reach the end from position i

ways(i) = ways(i+1) + ways(i+2) + ... + ways(i + a[i])

dp[i] = dp[i+1] + dp[i+2] + ... + dp[i + a[i]]

// Jumping on Numbers — number of ways (top-down, memoization)
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
vector<ll> dp;
vector<int> a;
int N;

ll ways(int i) {
    if (i == N - 1) return 1;
    if (dp[i] != -1) return dp[i];
    ll sum = 0;
    for (int k = 1; k <= a[i]; k++) {
        int nxt = i + k;
        if (nxt < N) sum += ways(nxt);
    }
    dp[i] = sum;
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    dp.assign(N, -1);
    cout << ways(0) << "\n";
    return 0;
}
    

Visual DP Table (Bottom-up Tabulation)

This is an illustration of how the DP table is filled for the example:

N = 4
a = [1, 2, 1, 1]

Reminder:
dp[i] = number of ways to reach the end (position N–1) from position i.

Step-by-step Table Filling

Final Result

dp[0] = 2 There are exactly two different ways to reach the last position.

Quick Explanation of Colors in the Table

• a[i] — jump values
• dp[i] — computed number of ways
• yellow — special key steps (base)

Challenging Problem (Competition Level): Generalized Fibonacci

Problem: K-bonacci Sequence

Given an integer K (2 ≤ K ≤ 20) and an integer N (1 ≤ N ≤ 2000). We define the K-bonacci sequence as follows:

• For the first K elements: F[1] = F[2] = ... = F[K] = 1
• For each subsequent element: F[n] = F[n-1] + F[n-2] + ... + F[n-K]

The task is to compute F[N] mod 1,000,000,007.

✔ Input

K N

✔ Output

One number – the value of F[N] mod 1e9+7.

Why is this problem challenging?

• The naive approach requires O(K·N), which is acceptable only for small N.
• A faster solution uses a sliding window so that each sum is O(1).
• For very large N, matrix exponentiation of dimension K×K is required.

Guidelines for a DP Solution

1. Create an array dp of length N and initialize dp[1…K] = 1.
2. For each n > K, compute:

   dp[n] = (dp[n-1] + dp[n-2] + ... + dp[n-K]) % MOD

3. For an optimal solution, use a sliding window:

   window_sum = dp[1] + dp[2] + ... + dp[K]
   
   for n from K+1 to N:
       dp[n] = window_sum
       window_sum = window_sum + dp[n] - dp[n-K]

Expected Knowledge

• Memoization and tabulation
• Sliding window over a DP array
• Modular arithmetic
• Memory optimization: O(N) → O(K)