Mastering Fibonacci Sequence with Dynamic Programming in JavaScript

12.2.1 Fibonacci Sequence (DP Approach)

The Fibonacci sequence is a classic problem that serves as an excellent introduction to dynamic programming (DP). This section will guide you through the process of optimizing the computation of the Fibonacci sequence using DP techniques in JavaScript, focusing on memoization and tabulation. By the end of this section, you will be able to apply these techniques to efficiently solve problems with overlapping subproblems and optimal substructure properties.

Understanding the Fibonacci Sequence

The Fibonacci sequence is defined as follows:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

This simple recursive definition leads to a straightforward recursive implementation, but it is not efficient for large n due to the exponential growth of recursive calls.

Naive Recursive Implementation

Let’s start by examining the naive recursive implementation of the Fibonacci sequence:

function fibonacciRecursive(n) {
    if (n <= 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

Inefficiency of Naive Recursion

The naive recursive approach has a time complexity of O(2^n), which is exponential. This inefficiency arises because the function repeatedly solves the same subproblems. For example, fibonacciRecursive(5) will compute fibonacciRecursive(3) twice, fibonacciRecursive(2) three times, and so on. This redundancy leads to a significant increase in computation time as n grows.

Dynamic Programming Approach

Dynamic programming offers a way to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. There are two main techniques in DP: memoization and tabulation.

Memoization

Memoization is a top-down approach that involves storing the results of expensive function calls and reusing them when the same inputs occur again. Here’s how you can implement the Fibonacci sequence using memoization:

function fibonacciMemoization(n, memo = {}) {
    if (n <= 1) {
        return n;
    }
    if (memo[n]) {
        return memo[n];
    }
    memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
    return memo[n];
}

Time Complexity: O(n)

Space Complexity: O(n)

Memoization reduces the time complexity from O(2^n) to O(n) by ensuring each subproblem is solved only once. The space complexity is also O(n) due to the storage of results in the memo object.

Tabulation

Tabulation, or the bottom-up approach, involves solving the problem iteratively and storing the results in a table (usually an array). This method can be more space-efficient than memoization:

function fibonacciTabulation(n) {
    if (n <= 1) {
        return n;
    }
    const fib = [0, 1];
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

Time Complexity: O(n)

Space Complexity: O(n)

In the tabulation method, we build the solution from the ground up, starting from the base cases and iteratively solving each subproblem. This approach also has a time complexity of O(n) but can be optimized further in terms of space.

Optimizing Space Complexity

While the tabulation method already improves space efficiency compared to memoization, we can further reduce space usage by keeping track of only the last two Fibonacci numbers:

function fibonacciOptimized(n) {
    if (n <= 1) {
        return n;
    }
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let next = a + b;
        a = b;
        b = next;
    }
    return b;
}

Space Complexity: O(1)

This optimized version maintains only two variables, a and b, to store the last two Fibonacci numbers, reducing the space complexity to O(1).

Comparing Implementations

To summarize, let’s compare the different implementations:

Practical Exercises

Now that you understand the different approaches to computing the Fibonacci sequence, try extending the Fibonacci function to compute large n values and observe the execution times and resource usage. Consider implementing a function that measures the time taken to compute Fibonacci numbers for increasing values of n and plot the results to visualize the efficiency of each method.

Challenge: Fibonacci for Large n

Implement a function that computes the Fibonacci sequence for large n (e.g., n = 1000000) using the optimized space approach. Measure the execution time and discuss the results.

function measureFibonacciExecutionTime(n) {
    const start = performance.now();
    const result = fibonacciOptimized(n);
    const end = performance.now();
    console.log(`Fibonacci(${n}) = ${result}`);
    console.log(`Execution time: ${end - start} milliseconds`);
}

measureFibonacciExecutionTime(1000000);

Conclusion

The Fibonacci sequence is a fundamental problem that illustrates the power of dynamic programming. By applying memoization and tabulation, we can transform an inefficient recursive solution into an efficient one. These techniques are not limited to the Fibonacci sequence but can be applied to a wide range of problems with overlapping subproblems and optimal substructure.

Further Reading

To deepen your understanding of dynamic programming and its applications, consider exploring the following resources:

• Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
• Dynamic Programming on LeetCode
• GeeksforGeeks Dynamic Programming Tutorial

Quiz Time!