Dynamic Programming

因為Shvara蛀牙了，那就來複習一些程式觀念吧，依照OKR的理念，我決定一開始就直接切入動態規劃。

我們知道動態規劃是問題中有相似子結構的問題，入門問題當然就是著名的Fibonacci。

背景知識

• 基礎程式語法

理解問題

給定一array, 每位數為前兩數和。

其實這也說明了子結構

如果要程式化，一開始可能會想到Quadratic時間的做法，而動態規劃除了相似子結構，另一個重點在記憶，可以儲存之前計算結果，用空間換取時間。

思路視覺化

F = [1,1,2,3,5,8]
1+1=2  
1+2=3

可以發現當i<2時都是1，而array從1開始
再來要有個迴圈走訪
最後是數值變換規則 i = i-1 + i-2 , i>=2

程式化

def fibonacci(n):
    F = {}
    F[0], F[1]=0, 1
    for i in range(2, n+1):  
       F[i]= F[i-1]+F[i-2]
    return F[n]  

複雜度分析

因為算完值都存入陣列，我們只有尋訪一次，儲存也是有多少值就存幾個。
TC: O(n)
SC: O(n)

問題

1. Kadane’s Algorithm
2. ZeroOne Knapsack
3. Unbound Knapsack

下次再介紹幾題好了

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)