一 、動態(tài)規(guī)劃做題套路總結：
-
dp[]數(shù)組的維度 -
dp[i]代表的含義是什么 - 最終的結果是
dp[n]還是fun( dp[] )玉掸，也就是要對dp數(shù)組做一個函數(shù)，如取dp數(shù)組中的最大值max dp[] - 弄清楚狀態(tài)轉移方程
常見的轉移方程
dp[i] = dp[i - 1] , dp[i - 2]
dp[i] = dp[i - j] , !dp[i - j]
etc
- 實在不行，就先列出dp數(shù)組的前幾項，然后找規(guī)律
二判族、做過的題目總結
建議按順序嘗試
簡單動態(tài)規(guī)劃
53 最大子序和
746 使用最小花費爬樓梯
1025 除數(shù)博弈
70 爬樓梯
中等動態(tài)規(guī)劃
650 只有兩個鍵的鍵盤
劍指offer63 股票的最大利潤
198 打家劫舍
221 最大正方形
931 下降路徑最小和
14 14- I. 剪繩子
62 不同路徑
高難動態(tài)規(guī)劃
32 最長有效括號
三、動態(tài)規(guī)劃優(yōu)化：
- 從前往后项戴，避免遞歸
- 空間優(yōu)化形帮，滾動數(shù)組 或者 常數(shù)級變量
四、目前還不太會的動態(tài)規(guī)劃
- 多維的動態(tài)規(guī)劃周叮，一看就很煩
例題 有哪些
- 有的不明所以沃缘，不知道
dp[][]應該代表什么例題有
- 有的不會寫狀態(tài)方程
例題有
