Python 學習演算法－動態規劃（Dynammic Programming）

動態規劃(Dynamic Programming)的基本思想是將複雜的問題分解為較小的子問題，並找到這些子問題的關聯性，通過這些子問題的解，我們可以避免重複計算，從而節省計算資源。這種過程稱為「記憶化(Memoization)」，通常使用數組或字典來實現，以在後續的計算中快速查找和重用中間結果。

範例－費波那契數

F(n) = 1 if n ≤ 1
F(n) = F(n-1) + F(n-2) else n​

若要以Python撰寫計算費波那契數，最簡單的寫法是直接根據方程式組寫成遞迴(Recursion)。

def fib(n):       
    return 1 if n <= 1 else fib(n - 1) + fib(n - 2)

這種寫法非常直觀，然而在實務上，我們會發現這個遞迴會重複計算我們已經計算過的答案，以fib(4)為例：

fib(4)

可以發現 fib(2) 被重複計算了兩次，當 n > 20 後，被重複計算的節點數量會非常可觀，為了改善這項問題，我們可以使用一個陣列來儲存算過的答案，這種技巧稱為「記憶化(Memoization)」，這邊我們使用 dp 這個陣列來儲存， dp[i] 代表 fib(i) 的答案：

def fib(n):
    dp = [None for _ in range(n + 1)]
    dp[0] = dp[1] = 1
    
    def solve(i):
        if not dp[i]:
            dp[i] = fib(i - 1) + fib(i - 2)
        
        return dp[i]
    
    return solve(n)

一樣以 fib(4) 為例：

fib(4)

可以發現因為fib(2)已經被算過了，我們就不用再下去遞迴了。

目前的做法，我們都是從 n 開始，一路向下遞迴，直到有答案在返回，這種作法稱為Top-Down，那是否有方法從 0 開始，一路算到 n 呢？答案是有的，我們可以利用迴圈，從 0 一路往上開始製表(Tabulation)，這種方法稱為Bottom-Up。

def fib(n):
    dp = defaultdict(int)
    dp[0] = dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

當我們使用Bottom-Up時，可以發現，當迴圈跑到 i 時，我們只會使用到 i - 1 與 i - 2 ， i - 3 以下則不會使用到了，也因此，我們只需要兩個變數，紀錄 i - 1 與 i - 2，並不對更新，並不用全部存起來，這時，我們可以使用另一個技巧－空間管理(Space Optimization)。

def fib(n):
    curr = prev = prevv = 1

    for i in range(2, n + 1):
        curr = prev + prevv
        prev, prevv = curr, prev

    return curr