Skip to content

Latest commit

 

History

History
22 lines (19 loc) · 1.25 KB

DP.md

File metadata and controls

22 lines (19 loc) · 1.25 KB

Dynamic Programming(動態規劃) Back

  • 當我們把分治的思想運用到優化問題上時, 我們稱之為動態規劃 (Dynamic Programming)
  • 當一個問題符合最優子結構 (問題的最優解求解可以推給子問題的最優解, 且子問題最優解間互相獨立)時, 我們就可以通過動態規劃來解決問題
  • 解決思路:
    • characterize the structure of the optimal solution. (important)
    • recursively define expressions.
    • compute the value of the solution in a bottom-up fashion. (避免重複計算)
    • construct the optimal solution using the computed information.

典型問題及算法

  • Assembly-line Scheduling Problem [details]
  • Matrix-chain Multiplication Problem [details]
  • Longest Common Sub-sequence Problem [details]
  • Max Sum Problem [details]
  • 0-1 Knapsack Problem [details]
  • Single-source Shortest Path Problem
  • All-Pairs Shortest Path Problem