Choose your language!

---

|

Fibonacci with Dynamic Programming & Memoization Explained | Recursion Guide

1. Introduction

The Fibonacci sequence is the most common introductory example used to explain dynamic programming.

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

Memory Note for Top-Down (Memoization)

In top-down (recursion + memoization) approaches, there are two main sources of memory usage:

1. Heap/heap-like memory for the table (memo) — an array where we store results of subproblems (e.g., vector<long long> memo(n+1)).
2. Recursive call stack — each recursive call consumes a stack frame. Stack depth in the worst case equals the recursion depth (for Fibonacci, approximately n).

Calculations and Estimates (How to Quickly Calculate Memory Usage)

1) Memo array size
If you use long long (8 bytes), memory for memo is roughly:

memory_memo ≈ (n + 1) * sizeof(long long)  // bytes

Examples:

• n = 10⁴ → ≈ 80,000 B ≈ 0.08 MB
• n = 10⁵ → ≈ 800,000 B ≈ 0.8 MB
• n = 10⁶ → ≈ 8,000,000 B ≈ 8 MB

2) Stack frame memory estimate
The size of a single stack frame varies significantly depending on: compiler, optimizations, number of local variables, and function parameters. We give approximate ranges per type:

// rough estimates (for approximation only)
frame ≈ 32 – 128 bytes (typical)
stack_memory ≈ frame * depth  // bytes
depth ≈ maximum recursion depth (for fib ≈ n)

Examples (assuming frame = 64 B):

• n = 1,000 → stack ≈ 64 KB
• n = 10,000 → stack ≈ 640 KB
• n = 100,000 → stack ≈ 6.4 MB

Operating System Limits (Practical Risk)

• Windows (default stack, main thread) often has about 1 MB of stack per thread (varies). Deep recursion of several thousand calls can cause stack overflow on Windows.
• Linux (glibc) default usually has 8 MB (or more), so it tolerates deeper recursion, but limits exist (e.g., n ≈ 100,000 will likely exceed stack).
• In addition to the stack, if memo is large (n ≥ 10⁶ with 8B per element → ≈ 8 MB), this can also lead to Memory Limit Exceeded (MLE) on platforms with restricted memory.

Practical Recommendations

• For N ≥ a few thousand — avoid deep recursion on Windows; prefer bottom-up (iterative) solutions.
• If you need a memo table, calculate memory usage before running: size_bytes = (n+1) * sizeof(long long) and compare with available memory (e.g., 256 MB limit).
• To maintain a top-down style while avoiding stack overflow — you can:
  • increase the stack at linking (not possible on all competitive servers),
  • convert recursion into an explicit stack simulation using your own vector/stack (heap),
  • or simply implement a bottom-up version that does not use recursion.
• In competitive programming — always check input limits (n, max values) and choose the safest approach (usually bottom-up or 1D optimization) to avoid TLE, MLE, or stack overflow.

Summary Table (Quick Estimate)

n	memo (≈ 8B per element)	stack (frame≈64B)	Note
10³	~8 KB	~64 KB	no issues on most systems
10⁴	~80 KB	~640 KB	OK, but Windows may be near limit
10⁵	~0.8 MB	~6.4 MB	possible MLE/stack on restricted systems
10⁶	~8 MB	~64 MB	high risk of MLE/stack overflow

When DP Is Not Applicable and Why It Doesn’t Always Work

Although the Fibonacci problem is an ideal example for dynamic programming, it is important to understand that DP is not a universal technique and cannot be applied to every recursion. For dynamic programming to make sense, two basic conditions must be met:

• Optimal substructure — the solution to the problem can be obtained by combining optimal solutions of its smaller subproblems.
  If the optimal solution of the whole problem does not clearly depend on the optimal solutions of its subproblems, DP will not work.
• Overlapping subproblems — different recursive paths repeat the same subproblems multiple times.
  If subproblems do not repeat (e.g., each recursive call leads to a completely new state), memoization does not save time.

In the case of Fibonacci, both conditions are met: each F(n) depends only on F(n−1) and F(n−2), and those subproblems repeat many times, so DP drastically speeds up the computation.

However, there are problems where recursion exists, but DP does not help: for example, if there is no overlapping of subproblems (e.g., standard binary search) or if there is no optimal substructure (e.g., some problems with global constraints).

Therefore, it is important for learners to understand that DP is not a “magic speed-up,” but a method that only works when the problem has the right structure. Fibonacci is a good example, but it should not create the false impression that memoization can be applied to every recursion.

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.

Enter n: Show Results Show Call Tree (only for n ≤ 6)

Naive Recursion

Number of function calls: --

Maximum recursion depth (stack): --

Note: naive recursion repeats subproblems exponentially.

Top-down (Memoization)

Number of function calls: --

Maximum recursion depth (stack): --

Memoization avoids repeated calculations — each index is computed at most once.

Call Tree (Naive Recursion)

The tree shows all recursive calls. Visible only for small n.

---

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.

Enter n: Show Table

---

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

Method	Speed	Memory	Number of Calls
Naive recursion	❌ Slowest (O(2ⁿ))	Small	Huge
Top-down (memoization)	✔ Fast (O(n))	Recursive stack + array	Medium
Bottom-up	✔ Fast (O(n))	O(n)	Few
Bottom-up O(1)	⭐ Fastest	Minimal	Minimal

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 and the DP approach with memoization!

Open Quiz

Mini Quiz: Do you understand DP application for Fibonacci?

1. What is the basic recursive relation for the number of ways to climb stairs?

ways(n) = ways(n-1) + ways(n-2)
ways(n) = ways(n-1) * ways(n-2)
ways(n) = n + ways(n-1)
Show Answer

2. What are the initial values for DP in top-down memoization?

ways(0) = 1, ways(1) = 1
ways(0) = 0, ways(1) = 1
ways(0) = 1, ways(1) = 0
Show Answer

3. What is the main advantage of memoization in top-down approach?

Prevents multiple computations of the same subproblems
Shortens the input array
Enables bottom-up filling
Show Answer

4. Why can the bottom-up version be more stable than top-down for large N?

Because it avoids deep recursion and stack overflow
Because it uses less memory for all arrays
Because it computes only the first half of the array
Show Answer

5. What is the time complexity of the top-down solution with memoization?

O(2^N)
O(N)
O(log N)
Show Answer

6. How can bottom-up DP be optimized to O(1) memory?

By storing only the last two computed numbers
By storing the entire DP array
By using the top-down function
Show Answer

□ Reset Quiz

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 Instructions Show / Hide Solution

Instructions — Solution Idea

• Define ways(n) as the number of ways to climb a staircase with n steps (from 0 to n).
• Consider the last move: to reach n, the last step could be from n-1 (1 step) or n-2 (2 steps).
• Conclusion: ways(n) = ways(n-1) + ways(n-2) — the same recurrence as the Fibonacci sequence.
• Initial conditions: ways(0) = 1 (one way: do nothing), ways(1) = 1.
• Direct recursion is exponential because it repeats the same calls. Solution: memoization (top-down) — store computed values in an array (or map) and return them if already computed.

Implementation Plan (Top-down)

1. Create a vector/array memo of size n+1 and initialize it with -1 (not computed).
2. If requesting ways(k) and memo[k] != -1, return memo[k].
3. If k ≤ 1, return 1 (base case).
4. Otherwise, compute recursively ways(k-1) and ways(k-2), sum them and store in memo[k].

Notes on Types and Limits

• The number of ways grows exponentially but for typical tasks (N ≤ 90) use long long. For very large N, modular arithmetic or BigInteger may be required.
• Top-down uses recursion (depth ≤ N). For very large N, a bottom-up iterative solution avoids recursion depth and is more stable.

Solution — C++ (Top-down Memoization)

Explanation before the code:

• The code uses a long long vector memo initialized with -1.
• The function ways returns the number of ways for a given k and uses memoization to avoid recomputation.
• Main function reads N, initializes memo, and prints the result.

Copy

// 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;
}
    

Complexity Analysis

• Time: O(N) — each index 0..N is computed at most once.
• Memory: O(N) for memo plus recursive stack depth O(N).

Alternative Solution — Bottom-up (Iterative)

Briefly: the bottom-up version fills the dp array from 0 to N. It can be optimized to O(1) memory using just two variables.

// 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;
}
    

Comparative Note

• Top-down is often faster to implement and easier to understand for problems with multiple state parameters.
• Bottom-up is non-recursive, usually uses less stack memory, and can easily be optimized to O(1) space when the transition depends only on a constant number of previous states.

Test Example

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 Instructions Show / Hide Solution

Instructions — Solution Idea

We have an array a[] of length N. From position i we can jump to any position:

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

As long as we stay within array bounds. We want to compute:

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

For each position, sum the ways from all possible jumps:

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

Base Case

• ways(N - 1) = 1 — if we are already at the last position, there is exactly one way.

Why DP?

In plain recursion, the function ways(i) is called many times. If there are many small jumps, branches overlap, giving exponential complexity.

Therefore, we use:

• Memoization (top-down) — store the result for each position.
• Tabulation (bottom-up) — start from the end and fill the DP table backwards.

Top-down Memoization Plan

1. Create a vector dp of size N and initialize with -1.
2. Implement the recursive function ways(i).
3. If dp[i] != -1, return the stored result.
4. If i == N - 1, return 1.
5. Otherwise, sum all ways(i + k) for 1 ≤ k ≤ a[i] and store the result.

Bottom-up Tabulation Plan

1. Create dp[] of length N.
2. Set dp[N - 1] = 1.
3. For i = N-2 down to 0, compute:

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

This gives the same solution without recursion.

Solution — C++ (Top-down Memoization)

This is the most intuitive solution, as it follows the direct problem definition.
Comments explain each step in detail.

Copy

// 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;
}
    

Code Explanation

• dp[i] stores the result for position i.
• If dp[i] is not -1, the result has already been computed.
• From position i, examine all legal jumps and sum the ways.
• Recursion continues until reaching N - 1.

Time and Space Complexity

• Time: O(N · K), where K is the average number of possible jumps.
• Memory: O(N) for dp + recursive stack.

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

Position i	a[i]	dp[i]	Explanation
3	1	1	base — last position
2	1	1	dp[2] = dp[3] = 1
1	2	2	dp[1] = dp[2] + dp[3] = 1 + 1 = 2
0	1	2	dp[0] = dp[1] = 2

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)

---

Previous
​|< Introduction to dynamic programming

Next
DP: Knapsack problem >|

---