# Leetcode 509. Fibonacci Number

## 題解

### DP 自底向上 (bottom up)

class Solution:
    def fib(self, n: int) -> int:
        # DP bottom up
        # Time complexity: O(n)
        # Space complexity: O(1)
        if n == 0:
            return 0
        n1 = 1 # 0(n1) + 1(n2) -> 原本的 n2 取代 n1 所以從 2 開始 n1 為 1
        n2 = 1 # 0 + 1 => 1 (n1 + n2) 下一個狀態
        #                決策樹
        # (n1) 0 + (n2) 1  => (n1) 1 + (n2) 1
        #    (next) 1            (next) 2
        for i in range(2,n):
            temp = n2 # 先把 n2 記下來，因為等下要先替換 n2 = next
            n2 = n1 + n2 # 替換 n2
            n1 = temp # 把原本的 n2 替換成 n1
        return n2

### 遞迴

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