一、定義

動態(tài)規(guī)劃（dynamic programming)簡稱DP，用于解決重疊子問題。

二、解題步驟

1、確定dp數(shù)組以及下標含義

2、確定狀態(tài)轉(zhuǎn)移方程

3、dp數(shù)組的初始化

題目有兩種可能，一種是要求背包恰好裝滿，一種是可以不裝滿（只要不超過容量就行）。

- 恰好裝滿。只需要初始化dp[0] 為 0， 其他初始化為負數(shù)即可。

- 可以不裝滿。 只需要全部初始化為 0，即可。

4、確定遍歷的順序

外層遍歷物品，還是外層遍歷容量；

以及容量從大到小遍歷，還是從小到大遍歷。

5、舉例檢驗

三、總結(jié)

遞歸和動態(tài)規(guī)劃都是將原問題拆成多個子問題然后求解，他們之間最本質(zhì)的區(qū)別是，動態(tài)規(guī)劃保存了子問題的解，避免重復計算。

動態(tài)規(guī)劃內(nèi)容很多，將從以下方面進行學習：

斐波拉契數(shù)列

背包（0-1背包，完全背包）。。。。。

參考資料：github分類詳解