動態(tài)規(guī)劃特性

• 重疊子問題
  子問題可能被多次用到，多次計(jì)算
• 最優(yōu)子結(jié)構(gòu)
  最優(yōu)子結(jié)構(gòu)性質(zhì)是指問題的最優(yōu)解包含其子問題的最優(yōu)解

形式

• 自上而下
  遞歸實(shí)現(xiàn)
• 自下而上
  遞推實(shí)現(xiàn)

常見類型

• 矩陣型
• 序列型
• 雙序列型
• 劃分型
• 區(qū)間型
• 背包型
• 狀態(tài)壓縮型

• 樹型

  
  

實(shí)現(xiàn)思路

1. 確定問題狀態(tài)是什么
   確定最后一步
   劃分子問題
2. 狀態(tài)轉(zhuǎn)移方程是什么
3. 狀態(tài)的初始值和邊界條件是什么
   初始值就是無法用轉(zhuǎn)移方程表示的特殊情況，需要手動定義
   邊界條件就是明確計(jì)算范圍，防止越界

4. 問題要求的最后答案是什么

   
   

使用場景

1. 求最大值/最小值
2. 求可不可行

3. 求方案總數(shù)

   
   

參考

如何理解動態(tài)規(guī)劃
動態(tài)規(guī)劃和貪心算法區(qū)別