動態規劃(Dynamic Programming)的基本思想是將複雜的問題分解為較小的子問題，並找到這些子問題的關聯性，通過這些子問題的解，我們可以避免重複計算，從而節省計算資源。這種過程稱為「記憶化(Memoization)」，通常使用數組或字典來實現，以在後續的計算中快速查找和重用中間結果。
範例－費波那契數
F(n) = 1 if n ≤ 1
F(n) = F(n-1) + F(n-2) else n
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
