Skip to main content

509. Fibonacci Number

https://leetcode.com/problems/fibonacci-number/

Python​

Top-Down DP with dict memory​

class Solution:
    def __init__(self):
        self.memory = dict()

    def fib(self, n: int) -> int:
        if n < 2:
            return n

        if n in self.memory:
            return self.memory[n]

        self.memory[n] = self.fib(n-1) + self.fib(n-2)

        return self.memory[n]

Top-Down DP​

  • Time: O(N)
  • Space: O(N)
from functools import cache

class Solution:
    @cache
    def fib(self, n: int) -> int:
        if n < 2:
            return n

        return self.fib(n-1) + self.fib(n-2)

Bottom-Up DP​

  • Time: O(N)
  • Space: O(N)
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0

        dp = [None] * (n+1)
        dp[0], dp[1] = 0, 1

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

        return dp[n]

Bottom-Up DP with linear cache​

  • Time: O(N)
  • Space: O(1)
class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n

        pre_2, pre_1 = 0, 1

        for i in range(2, n+1):
            current = pre_1 + pre_2
            pre_2, pre_1  = pre_1, current

        return pre_1

Rust​

impl Solution {
    pub fn fib(n: i32) -> i32 {
        if n < 2 {
            return n;
        }

        let mut pre1 = 1;
        let mut pre2 = 1;

        for _ in 2..n {
            let current = pre1 + pre2;
            pre2 = pre1;
            pre1 = current;
        }
        return pre1;
    }
}

Javascript​

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