動態規劃 (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:知道順序,迴圈。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。