動態規劃 (DP)

DP

• Dynamic Programming
• 大問題 → 小問題
• 算過一次不再重算(空間換取時間)

DP三大步驟

1. 訂定小問題。(dp(n) 第n階方法數)
2. 找出轉移式。(dp(n)=dp(n-1)+dp(n-2))
3. 處理基底狀態。(dp(1)=1, dp(2)=2)

DP方式

• Top-Down：發現小問題還沒被算，遞迴。
• Bottom-Up：知道順序，迴圈。