一、定義
動(dòng)態(tài)規(guī)劃（dynamic programming)簡稱DP脸爱，用于解決重疊子問題遇汞。
二、解題步驟
1簿废、確定dp數(shù)組以及下標(biāo)含義
2空入、確定狀態(tài)轉(zhuǎn)移方程
3、dp數(shù)組的初始化
題目有兩種可能族檬，一種是要求背包恰好裝滿歪赢，一種是可以不裝滿（只要不超過容量就行）。
- 恰好裝滿单料。只需要初始化dp[0] 為 0埋凯， 其他初始化為負(fù)數(shù)即可点楼。
- 可以不裝滿。 只需要全部初始化為 0白对，即可掠廓。
4、確定遍歷的順序
外層遍歷物品甩恼，還是外層遍歷容量蟀瞧；
以及容量從大到小遍歷，還是從小到大遍歷媳拴。
5黄橘、舉例檢驗(yàn)
三、總結(jié)
遞歸和動(dòng)態(tài)規(guī)劃都是將原問題拆成多個(gè)子問題然后求解屈溉，他們之間最本質(zhì)的區(qū)別是塞关，動(dòng)態(tài)規(guī)劃保存了子問題的解，避免重復(fù)計(jì)算子巾。
動(dòng)態(tài)規(guī)劃內(nèi)容很多帆赢，將從以下方面進(jìn)行學(xué)習(xí)：
斐波拉契數(shù)列
背包（0-1背包，完全背包）线梗。椰于。。仪搔。瘾婿。
參考資料：github分類詳解
