動(dòng)態(tài)規(guī)劃特性
- 重疊子問(wèn)題
子問(wèn)題可能被多次用到谣膳，多次計(jì)算 - 最優(yōu)子結(jié)構(gòu)
最優(yōu)子結(jié)構(gòu)性質(zhì)是指問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解
形式
- 自上而下
遞歸實(shí)現(xiàn) - 自下而上
遞推實(shí)現(xiàn)
常見(jiàn)類(lèi)型
- 矩陣型
- 序列型
- 雙序列型
- 劃分型
- 區(qū)間型
- 背包型
- 狀態(tài)壓縮型
-
樹(shù)型
實(shí)現(xiàn)思路
- 確定問(wèn)題狀態(tài)是什么
確定最后一步
劃分子問(wèn)題 - 狀態(tài)轉(zhuǎn)移方程是什么
- 狀態(tài)的初始值和邊界條件是什么
初始值就是無(wú)法用轉(zhuǎn)移方程表示的特殊情況辽幌，需要手動(dòng)定義
邊界條件就是明確計(jì)算范圍觉吭，防止越界 -
問(wèn)題要求的最后答案是什么
使用場(chǎng)景
- 求最大值/最小值
- 求可不可行
-
求方案總數(shù)
