前情提要

因為昨天submit後,時間和空間的結果都很差,仔細想了想應該是因為遞迴的關係,所以今天想來研究下其他人的寫法

進入正題

在參考1連結中,雖然不是使用python語言,但提供了很多種解法的思路,除了遞迴的方式之外,還有另外3種解法:
1.建立一個陣列,用陣列紀錄所有計算過的費波那契數
2.用變數的方式記錄前兩個費波那契數
3.因為這題leetcode題目中有提到輸入的數字範圍,所以直接hardcode範圍內的費波那契數
因為我很好奇這三種方法在submit後的時間和空間的結果上可以進步多少,所以我用了他提供的解法邏輯寫:

-陣列的方式

def fib(self, N: int) -> int:
    Fibo=[0,1]
    for i in range(2, N+1):
        Fibo.append(Fibo[i-1] + Fibo[i-2])
    return Fibo[N]

結果

-變數的方式

def fib(self, N: int) -> int:
    if N < 2:
        return N
    previous1 = 0
    previous2 = 1
    for i in range(2, N+1):
        sum = previous1 + previous2
        previous1 = previous2
        previous2 = sum
    return previous2

結果

-Hardcode

def fib(self, N: int) -> int:
    Fibo=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
    return Fibo[N]

結果

比較表:

從上面runtime和memory的結果上來看,用變數的方式兩種都是最少的,這個應該是和時間複雜度和空間複雜度的計算有相關,明天來研究這個.

參考資料

參考1[LeetCode] Fibonacci Number 斐波那契数字