leetcode 509. fibonacci-number - IHCT Blog - 遨遊星辰Among The Stars

費波那契數列

可延伸：dynamic programming、recursion

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

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

遞迴解 Recursion

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

因為是遞迴解，每次都要重複call自己的function好幾次，並且透過觀察就可以知道，以n=5為舉例，fib(3)會被call兩次，所以速度當然非常慢。要遞迴兩個函數，每次都要重複兩個子funciton，所以時間複雜度為**O(2^n)，空間複雜度為O(n)**。

DP解 Dynamic Programming

動態編程的目的就是用空間換取時間，只要每次運算完先把數值記憶起來，下一ˊ次計算再把數值出來就好，這樣就可以省下call function的時間！

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

        return table[n]

因為我們預先建立了一個名為table的list，然後每次都從table提數值出來，計算完再把數值存到table裡面，所以時間複雜度為**O(n)，空間複雜度為O(n)**。

迭代解 Iteration

跟dp解差不多，只是我們並沒有先建好table，而是計算完就append到table，不過儲存的邏輯是一樣的。

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

        return table[n]

變數解 Variable

講到list，第一個想到的就是mutable，但是如果我們今天只是存在變數裡呢？不需要讓table存下計算過程所有的解，而是專注在答案。優點是空間複雜度變小，缺點是無法提取計算過的數字。

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

        return ans

因為計算邏輯都一樣，時間複雜度仍然為**O(n)，但我們只用三個變數來執行這個功能，每次都是直接從變數取出來，不需要占用儲存空間，所以空間複雜度為O(1)**。