這篇文章主要記錄動態規劃方面的學習。

動態規劃的核心思想：

把大問題分解成小問題，記住小問題的解，避免重復計算。

動態規劃(DP)的三大特點：

①最優子結構：大問題的最優解可以由小問題的最優解推導出來

②重疊子問題：在求解過程中會反復遇到相同的小問題

③無后效性：當前狀態一旦確定，后續過程不受之前決策的影響

---

??0-1背包問題

?? 生活化題目：吃貨的購物計劃

題目：媽媽給你一個限重5kg的購物袋，超市有以下零食：

零食	重量	好吃度
薯片	2kg	4
可樂	3kg	5
糖果	1kg	3
餅干	2kg	3

規則：

1. 購物袋不能超重（≤5kg）

2. 每種零食只能拿一件

3. 目標是讓總"好吃度"最高

?? 分步思考圖解

第0步：初始化表格（空包狀態）

容量	0kg	1kg	2kg	3kg	4kg	5kg
價值	0	0	0	0	0	0

第1步：考慮薯片（2kg，好吃度4）

if 當前容量 >= 2kg:價值 = max(不裝的價值, 裝的價值 = 剩余容量的價值 + 4)

容量	0kg	1kg	2kg	3kg	4kg	5kg
價值	0	0	4	4	4	4

第2步：加入可樂（3kg，好吃度5）

# 容量3kg時：
max(不裝=4, 裝=0kg價值0 + 5 =5) → 選5
# 容量5kg時：
max(不裝=4, 裝=2kg價值4 +5=9) → 選9

容量	0kg	1kg	2kg	3kg	4kg