動態規劃 DP
動態規劃 Dynamic Programming (DP)
是一種 演算方法
(解決問題的通用策略或框架，他不是一個固定的、單一的演算法)
DP 通常包含
- 狀態：
- 狀態轉移：從 已知狀態 算出 未知狀態
- 狀態初始值：計算開始前已知的狀態
- 狀態計算順序：
DP 適用狀況
最佳子結構性質
如果問題的最佳解所包含的子問題的解也是最佳的，我們就稱該問題具有最佳子結構性質（即滿足最佳化原理）。最佳子結構性質為動態規劃演算法解決問題提供了重要線索。
無後效性
子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。
子問題重疊性質
子問題重疊性質是指在用遞迴演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地檢視一下結果，從而獲得較高的效率，降低了時間複雜度。
分析 DP
分析怎麼表示一個「狀態」
…
分析怎麼從 已知狀態 得出 未知狀態
…
代碼實現
遞迴 + 記憶化
記憶化搜索 有時候被獨立為一種算法
但它其實是 DP 的一種
…
順 迭代
…
逆 迭代
…
動態規劃的模型分類大概有以下幾個：
線性 DP
費波那契數
數位 DP
數位 DP 問題往往長做
給一個區間 [l, r]，求這個區間中滿足 *$%(@ 條件的值的個數
背包 DP
背包問題是種選擇問題（組合優化問題）
背包 DP 通常題目長做
#@!&* 在 %^#$ 的條件下
從多個選項中選擇 個 &^#$
求最優的 某個值（如 最大值、最少個數、最多方法數…）
以 「b184. 5. 裝貨櫃問題」 舉例
題目：https://zerojudge.tw/ShowProblem?problemid=b184
現在一共有若干項貨品可選擇運載
每一項 k 都有一個已知的體積 v[k]，以及載運的利潤 c[k]
但是貨櫃的總容量是100，可能無法將貨物全部裝入
希望選出其中的若干項，其體積總和不超過100，使得利潤最大
這就是所謂的「選擇問題」
(這裡先不解題，只是看看這類題目的樣子)
(先有個概念，知道背包系列題目到底在干什麼)
另外背包問題還能細分成
| 問題 | 描述 |
|---|---|
| 01 背包 | 每件物品只有一个（每件物品要嘛装，要嘛不装，只有兩種狀態，故稱 01 背包） |
| 完全背包 | 每個物品有無限個，可以多次選取 |
| 多重背包 | 每個物品有 k 個，最多選取 k 次 （不同物品的個數可能不同） |
| 分組背包 | 物品被分成 n 組，每組有 m 種物品，對於每組最多只能選一個物品 |
b184. 5. 裝貨櫃問題 就是個「01 背包問題」
題目
01 背包
b184. 5. 裝貨櫃問題
474. 一和零
416. 分割等和子集
494. 目标和
1049. 最后一块石头的重量 II
完全背包
518. 零钱兑换 II
377. 组合总和 IV
多重背包
分組背包
區間 DP
區間 DP 這類問題的本質是：
在一個區間上進行某種操作或選擇
目標是最小化/最大化某個值
這類題目通常長做
對一個區間（如一段字串、數列）
進行 %!@& 操作，在滿足 @#^$ 的條件下
求最小或最大結果