Fibonacci Number

• Difficulty: Easy
• Type: Dynamic Programming
• link

Problem

Solution

• Brute force recursion solution

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        else:
            return self.fib(n-1) + self.fib(n-2)

• Memoization (Top-Down) solution

import collections
class Solution:
    dp = collections.defaultdict(int)
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        if self.dp[n]:
            return self.dp[n]
        self.dp[n] = self.fib(n-1) + self.fib(n-2)

        return self.dp[n]

• Tabulation (Bottom-Up) solution

import collections
class Solution:
    dp = collections.defaultdict(int)
    def fib(self, n: int) -> int:
        self.dp[1] = 1

        for i in range(2,n+1):
            self.dp[i] = self.dp[i-1] + self.dp[i-2]

        return self.dp[n]

• Minimum space complexity solution

class Solution:
    def fib(self, n: int) -> int:
        x,y = 0,1
        for _ in range(n):
            x,y = y, x+y
        return x