上一章我們帶大家看過Divide and Conquer(D&C)，今天要來介紹演算法中非常重要的動態規劃求解Dynamic Programming(DP)，在這裡我們的programming並不是指coding的意思，而是指數學形式上最佳化的機制，而說到DP就不能不提到兩個重要的方法(1) Memorization (2) Iteration

Weighted Interval Scheduling是動態規劃求解的經典問題，我們在interval schedule里求取互相compatiable之下，總和最大的值。根據結束時間排序，再從中選出程序，使價值總和最大。這個做法要考慮一件事，就是最後一個程序會不會包含在最佳解中？隨著問題的答案變化，induction 要切分出來的時間刻度就會不同，因此不適合拿來當基準。

1. 自頂向下的記憶化（Memoization）

自頂向下的記憶化是一種遞歸方法，將已經計算過的結果存儲起來，以避免重複計算。這種方法通常伴隨著遞歸調用，每當需要計算某個子問題時，首先檢查這個子問題是否已經被計算過，如果已經計算過，就直接返回已存儲的結果。

透過遞歸來定義問題的解，使用一個數組或字典來存儲已經計算過的子問題結果，每次遞歸計算前，先檢查結果是否已經存在；如果存在則直接返回，否則計算並存儲結果。

代碼範例：費氏數列

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(10))  # Output: 55

2. 自底向上的迭代（Iteration）

自底向上的迭代方法是通過構建一個表格來從底層開始逐步計算出問題的解。這種方法通常避免了遞歸調用，直接利用迴圈來計算每個子問題，並最終得到原問題的解。

根據問題的大小初始化一個數組或表格，按照狀態轉移方程，從最小的子問題開始計算，逐步填充整個表格，最終表格中的某個值就是問題的最優解。

代碼範例：費氏數列

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib(10))  # Output: 55