1. 背包問(wèn)題
01背包
基本狀態(tài)：f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值
基本轉(zhuǎn)移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}，解釋：前i-1件物品放入剩下的容量為v-c[i]的背包中
初始化：1. 要求恰好裝滿背包唁奢，那么在初始化時(shí)除了f[0]為0其它f[1..V]均設(shè)為-∞， 2.沒(méi)有要求必須把背包裝滿，而是只希望價(jià)格盡量大，初始化時(shí)應(yīng)該將f[0..V]全部設(shè)為0
完全背包
基本狀態(tài)：f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值
基本轉(zhuǎn)移方程：f[i][v]=max{ f[i-1][v-k*c[i]] + k*w[i] | 0<=k*c[i]<=v }
優(yōu)化轉(zhuǎn)移方程： f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
實(shí)現(xiàn)：
for i=1..N
for v=0..V # 對(duì)于i個(gè)物品盗飒，v的大小麻敌，循環(huán)添加當(dāng)前物品
f[v]=max{f[v],f[v-cost]+weight}
當(dāng)我們把i從1到N循環(huán)時(shí)，f[v]表示容量為v在前i種背包時(shí)所得的價(jià)值际歼，這里我們要添加的不是前一個(gè)背包，而是當(dāng)前背包姑蓝。所以我們要考慮的當(dāng)然是當(dāng)前狀態(tài)鹅心。
多重背包
基本狀態(tài)：f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值
基本轉(zhuǎn)移方程： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
優(yōu)化實(shí)現(xiàn)：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
混合三種背包問(wèn)題
有的物品只可以取一次（01背包），有的物品可以取無(wú)限次（完全背包）它掂，有的物品可以取的次數(shù)有一個(gè)上限（多重背包）
for i=1..N
if 第i件物品屬于01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品屬于完全背包
CompletePack(c[i],w[i])
else if 第i件物品屬于多重背包
MultiplePack(c[i],w[i],n[i])
二維費(fèi)用的背包問(wèn)題
轉(zhuǎn)移狀態(tài)方程（加上一個(gè)向度）：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
分組的背包問(wèn)題
有N件物品和一個(gè)容量為V的背包巴帮。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]虐秋。這些物品被劃分為若干組榕茧，每組中的物品互相沖突，最多選一件客给。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量用押，且價(jià)值總和最大。
狀態(tài)：f[k][v]表示前k組物品花費(fèi)費(fèi)用v能取得的最大權(quán)值
狀態(tài)轉(zhuǎn)移方程：f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于組k}
for 所有的組k
for v=V..0
for 所有的i屬于組k
f[v]=max{f[v],f[v-c[i]]+w[i]}
以下來(lái)源于九章算法課件 -- jiuzhang.com
- 狀態(tài) State （靈感靶剑，創(chuàng)造力蜻拨，存儲(chǔ)小規(guī)模問(wèn)題的結(jié)果) 何時(shí)用dp池充？
- 最優(yōu)解/Maximum/Minimum
- Yes/No
- Count(*)
- 方程 Function
- 狀態(tài)之間的聯(lián)系，怎么通過(guò)小的狀態(tài)缎讼，來(lái)求得大的狀態(tài)
- 初始化 Intialization
- 最極限的小狀態(tài)是什么, 起點(diǎn)
- 答案 Answer
- 最大的那個(gè)狀態(tài)是什么收夸，終點(diǎn)
題目類型1
利用滾動(dòng)數(shù)組對(duì)空間的優(yōu)化（從小朝大遞推）
題目類型2
記憶化搜索 （從大朝小遞推）什么時(shí)候用？
- 狀態(tài)轉(zhuǎn)移特別麻煩血崭，不是順序性卧惜。
- 初始化狀態(tài)不是很容易找到。
題目類型3
區(qū)間類DP, 特點(diǎn)：
- 求一段區(qū)間的解max/min/count
- 轉(zhuǎn)移方程通過(guò)區(qū)間更新
- 從大到小的更新
題目類型4
雙序列動(dòng)態(tài)規(guī)劃
state: f[i][j]代表了第一個(gè)sequence的前i個(gè)數(shù)字/字符夹纫，配上第二個(gè)sequence的前j個(gè)...
- function: f[i][j] = 研究第i個(gè)和第j個(gè)的匹配關(guān)系
- initialize: f[i][0] 和 f[0][i]
- answer: f[n][m] min/max/數(shù)目/存在關(guān)系
- n = s1.length()
- m = s2.length()
題目類型5
背包類DP咽瓷，特點(diǎn)：
- 用值作為DP維度
- DP過(guò)程就是填寫矩陣
- 可以滾動(dòng)數(shù)組優(yōu)化
