Fibonacci Number

TARGET DECK: Leetcode FILE TAGS: Easy

---

Intuition

• On each iteration, you collect the previous house and the one before that one.
• To do bottom up, notice what bottom means: each respective subroutine is the fibonacci number at that index.
• And you need not tabulate, since you can just keep track of the i - 1 and i - 2 indices, respectively.

Complexity

Runtime

$O(N)$ since we are just doing one computation on each subroutine.

Space

$O(1)$ since we need not tabulate.

Code

No Extra Space

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        before, after = 0, 1
        for i in range(n + 1 - 2):
            before, after = after, before + after
        return after

Tabulation

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        sp = [0] * (n + 1)
        sp[0], sp[1] = 0, 1
        for i in range(2, n + 1):
            sp[i] = sp[i - 1] + sp[i - 2]
        return sp[n]

Top Down

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

Notes

Cards

START Basic Front: Fibonacci Number Back: Keep track of i - 1 and i - 2 indices, keeping in mind that you stop at exactly the nth number.

END

---

References

• Fibonacci Number