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

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)