Dynamic Programming

一個有效率的方法，可以找出最佳解，對付“multi-stage decision problem”

• 應用： 1.LCS (Longest common subsequence) 2.Edit distance 3.Matrix chain products 4.All-pair shortest distance 5.Dynamic time warping 6.Hidden Markov model

• 問題特色
  1.Decomposition
  大問題可以分解成小問題
  2.Subproblem optimality
  小問題可以算出最佳解，且可以組合為大問題的最佳解

• DP三步驟
  1.Define optimum-value function
  2.寫成遞回形式（recurrent formula）
  3.指定答案（optimum-value function 的表示式）

• 範例--Optimal Path Finding
  記得要加上back tracking information

• 觀察
  1.若找到t(k)，則所有小於k的問題都找到答案
  2.multi-stage，一層一層找出，沒有loop
  3.任何DP問題都可以visualize為Optimal Path Finding問題

• 特性
  1.要存back tracking information，記錄下走過的路
  2.大問題解決的話，小問題也解決了
  3.能找出最佳路徑，若要找第二佳的則很麻煩（n-best）