1718192021222324252627

class Solution:
    # Function to calculate Fibonacci using tabulation
    def fib(self, n):
        # If n is 0 or 1, return n
        if n <= 1:
            return n

        # Create dp array
        dp = [0] * (n + 1)

        # Initialize base cases
        dp[0] = 0
        dp[1] = 1

        # Fill dp array iteratively
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        # Return final answer
        return dp[n]

# Driver
if __name__ == "__main__":
    n = 10
    sol = Solution()
    print(sol.fib(n))

12345678910111213141516171819202122232425262728

class Solution {
    // Function to calculate Fibonacci using tabulation
    fib(n) {
        // If n is 0 or 1, return n
        if (n <= 1) return n;

        // Create dp array
        let dp = new Array(n + 1).fill(0);

        // Initialize base cases
        dp[0] = 0;
        dp[1] = 1;

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

        // Return final answer
        return dp[n];
    }
}

// Driver
const n = 10;
const sol = new Solution();
console.log(sol.fib(n));

Part 3: Space Optimization

If we closely look at the relation,

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

we see that for any i, we do need only the last two values in the array. So is there a need to maintain a whole array for it? The answer is ‘No’. Let us call dp[i-1] as prev and dp[i-2] as prev2. Now understand the following illustration.

Each iteration’s cur_i and prev becomes the next iteration’s prev and prev2 respectively.
Therefore after calculating cur_i, if we update prev and prev2 according to the next step, we will always get the answer.
After the iterative loop has ended we can simply return prev as our answer.

Code

<