動態規劃的概念

• 狀態：也就是DP數組的定義

• 狀態轉移

dp五部曲的理解

見：代碼隨想錄

• 優先確定：狀態的定義，狀態轉移的房產

• 根據狀態轉移方程確定：遍歷順序，初始化

狀態壓縮

• 本質上就是變量個數減少，狀態定義更加簡單

• 初始化和遍歷順序也要考慮

---

動態規劃的定義理解:

重復子問題，狀態，狀態轉移

• P1216 [IOI 1994] 數字三角形 Number Triangles

動態規劃的起源：記憶化搜索

記憶化搜索本質是對回溯搜索的一種優化，很多時候先想到回溯，由回溯想到記憶化搜索，再想到動態規劃

• P1434 [SHOI2002] 滑雪
• P4017 最大食物鏈計數

圖搜索問題中的動態規劃

• P1002 [NOIP 2002 普及組] 過河卒 :邊界條件+數組拷貝

0-1 背包問題

背包問題的應用

經典背包問題

• P1048 [NOIP 2005 普及組] 采藥
  
• P1802 5 倍經驗日:這個背包問題需要考慮dp[0]的情況

價值等于重量：是否恰好裝滿背包

• 416. 分割等和子集
• 1049. 最后一塊石頭的重量 II
• 494.目標和

三維DP：

• 474. 一和零

---

完全背包問題

• 物體可以重復使用無限次

• 區別是:是否能利用剛更新的狀態

• 轉換為0-1背包問題

例題：

• 52. 攜帶研究材料（第七期模擬筆試）
• 518. 零錢兌換 II
• 322. 零錢兌換
• 279.完全平方數

背包問題的理解：遍歷順序

• 一般來說，先遍歷背包還是物體,順序不重要，更取決于遞推公式。

• 對于一些問題(排列或組合)，遍歷順序影響答案。

例題

• 377. 組合總和 Ⅳ:換順序后，前面的物體有機會重新考慮(排序)
• 139.單詞拆分:潛在考慮單詞順序

---

多重背包問題

---

線性動態規劃

• P1115 最大子段和：引用背包問題的定義，維護虛假的序列和