動態規劃 (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:把所有範圍內的子問題算過一次,迴圈,要知道順序。

分享文章!
發佈留言

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