斐波納契數

Fibonacci 數是動態規劃的主要主題，因為傳統的遞迴方法會進行大量的重複計算。在這些例子中，我將使用 f(0) = f(1) = 1 的基本情況。

這是 fibonacci(4) 的示例遞迴樹，請注意重複的計算： https://i.stack.imgur.com/CLwKE.jpg

非動態程式設計 O(2^n) 執行時複雜度，O(n) 堆疊複雜度

def fibonacci(n):
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

這是編寫問題最直觀的方法。當你下降第一個遞迴分支來呼叫 fibonacci(n-1) 直到你擊中基本情況 n < 2 時，最多堆疊空間將是 O(n)。

這裡可以看到 O(2^n) 執行時複雜性證明： Fibonacci 序列的計算複雜性 。要注意的要點是執行時是指數的，這意味著每個後續項的執行時間將加倍，fibonacci(15) 將是 fibonacci(14) 的兩倍。

memoized O(n) 執行時複雜度，O(n) 空間複雜度，O(n) 堆疊複雜度

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

通過 memoized 方法，我們引入了一個可以被認為是所有先前函式呼叫的陣列。memo[n] 的位置是函式呼叫 fibonacci(n) 的結果。這允許我們為 O(n) 執行時交換 O(n) 的空間複雜度，因為我們不再需要計算重複的函式呼叫。

迭代動態程式設計 O(n) 執行時複雜度，O(n) 空間複雜度，無遞迴堆疊

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

如果我們將問題分解為它的核心元素，你會注意到為了計算 fibonacci(n)，我們需要 fibonacci(n-1) 和 fibonacci(n-2)。我們還注意到，我們的基本情況將出現在遞迴樹的末尾，如上所示。

有了這些資訊，現在有必要向後計算解決方案，從基礎案例開始向上計算。現在為了計算 fibonacci(n)，我們首先計算到 n 之前的所有斐波納契數。

這裡的主要好處是我們現在已經消除了遞迴堆疊，同時保持了 O(n) 執行時。不幸的是，我們仍然有一個複雜的空間複雜性，但也可以改變。

高階迭代動態程式設計 O(n) 執行時複雜度，O(1) 空間複雜度，無遞迴堆疊

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

如上所述，迭代動態程式設計方法從基本情況開始並且工作到最終結果。為了使空間複雜度達到 O(1)（常數）所做的關鍵觀察是我們為遞迴堆疊做的相同觀察 - 我們只需要 fibonacci(n-1) 和 fibonacci(n-2) 來構建 fibonacci(n)。這意味著我們只需要在迭代中的任何一點儲存 fibonacci(n-1) 和 fibonacci(n-2) 的結果。

為了儲存這最後兩個結果，我使用一個大小為 2 的陣列，並簡單地使用 i % 2 翻轉我指定的索引，i % 2 將交替使用：0, 1, 0, 1, 0, 1, ..., i % 2。

我將陣列的兩個索引一起新增，因為我們知道新增是可交換的（5 + 6 = 11 和 6 + 5 == 11）。然後將結果分配給兩個點中的較舊點（由 i % 2 表示）。然後將最終結果儲存在 n%2 位置

筆記

• 重要的是要注意，有時最好為重複執行大型計算的函式提出迭代的 memoized 解決方案，因為你將建立一個函式呼叫的答案快取，如果已經有後續呼叫可能是 O(1) 已被計算。