什么情況下使用動(dòng)態(tài)規(guī)劃
滿足下面三個(gè)條件之一胰柑，則極有可能使用動(dòng)態(tài)規(guī)劃90%-95%：
- 求最大值，最小值
- 判斷方案是否可行
- 統(tǒng)計(jì)方案個(gè)數(shù)
極不可能使用動(dòng)態(tài)規(guī)劃的情況：
- 求出所有具體方案而非方案的個(gè)數(shù)（要用DFS而不是DP）
- 輸入數(shù)據(jù)是一個(gè)集合而不是序列
- 暴力算法已經(jīng)是多項(xiàng)式級別
DP 擅長將暴力情況下復(fù)雜度為O(n!)和O(2^n) 的優(yōu)化為O(n^2) 或O(n^3) ,
若原本暴力算法就是O(n^2) 或O(n^3) , 則沒有多少優(yōu)化的空間
動(dòng)態(tài)規(guī)劃的4點(diǎn)要素
- 狀態(tài)State
靈感惶岭，創(chuàng)造力刹孔，存儲小規(guī)模問題的結(jié)果
- 最優(yōu)解 / Maximum / Minimum
- Yes / No
- Count(*)
- 方程 Function
狀態(tài)之間的聯(lián)系，怎么通過小的狀態(tài)溪食，來求得大的狀態(tài) - 初始化 Initialization
最極限的小狀態(tài)是什么鼓拧，起點(diǎn) - 答案 Answer
最大的那個(gè)狀態(tài)是什么区岗，終點(diǎn)
常見的動(dòng)態(tài)規(guī)劃類型及狀態(tài)特點(diǎn)
坐標(biāo)型，單序列毁枯，雙序列慈缔，劃分型，背包型种玛，區(qū)間型藐鹤，博弈型
