Fibonacci number

Let’s evaluate the Classic Dynamic Programming problem, Fibonacci Number in a crispy way.

We will start solving the problem from a recursive solution and later step by step we will use memoization and space optimization.

The Fibonacci Number or Fibonacci Sequence is as follows,

0, 1, 1, 2, 3, 5, 8, 13 and so on.

After the first two numbers, each number is the sum of the previous two numbers.

Recursive Solution

So, the constant part of the base case of the sequence is first two numbers are always 0 and 1. To calculate the rest of the numbers we will consider,

f(n) = f(n - 1) + f(n - 2)

With the base case and driven formula, our recursive solution will be,

function fibonacciNumber(n: number): number {
    const dp = new Array(n + 1).fill(-1);
    const helper = (step) => {
        if (dp[step] !== -1) {
            return dp[step];
        }

        if (step === 0 || step === 1) {
            return step;
        }

        const first = helper(step - 1);
        const second = helper(step - 2);

        dp[step] = first + second;

        return dp[step];
    }

    return helper(n);
};

This is a bottom-up approach. However, if we go to a tabulation format, we can design a top-to-bottom approach.

Memoization

We are maintaining an array dp where we are keeping the sequence number. After the first two values, the next one is the sum of the previous two values. In a more simplified way, we can say,

dp[n] = dp[n - 1] + dp[n - 2]

Now, the first two values are known and we will update these two values initially. Then with a simple loop we will calculate the rest of the sequence.

function fibonacciNumber(n: number): number {
    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i += 1) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
};

With the implementation, we can see the space complexity is O(n). With this in mind, can we do more space optimization?

Space Optimization

Since each of the values just depends on the previous two values, we can just keep these previous two values and calculate the current one.

function fibonacciNumber(n: number): number {
     if (n < 2) {
        return n;
    }
    let prev1 = 0;
    let prev2 = 1;

    for (let i = 2; i <= n; i += 1) {
        const temp = prev2;
        prev2 = prev1 + prev2;
        prev1 = temp;
    }

    return prev2;
};

With these constant values, now, we can now optimize the space to O(n)

Fibonacci Number: From recursion to memoization and ultimately space-optimized solution

Comments

Node.js & JavaScript

Practical Closure

More from this blog

The Comprehensive Guide to REST API Architecture and Conventions

JavaScript Loading Strategies in Web Page: async and defer

DOM Positioning

CSS Selector Specificity

Understanding CSS Display Property

Recursive Solution

Memoization

Space Optimization

Command Palette

Comments

Node.js & JavaScript

Practical Closure

More from this blog

Recursive Solution

Memoization

Space Optimization