1. 背包问题
01背包
基本状态：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值
基本转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}，解释：前i-1件物品放入剩下的容量为v-c[i]的背包中
初始化：1. 要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞， 2.没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0
完全背包
基本状态：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值
基本转移方程：f[i][v]=max{ f[i-1][v-k*c[i]] + k*w[i] | 0<=k*c[i]<=v }
优化转移方程： f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
实现：
for i=1..N
for v=0..V # 对于i个物品，v的大小，循环添加当前物品
f[v]=max{f[v],f[v-cost]+weight}
当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。
多重背包
基本状态：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值
基本转移方程： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
优化实现：
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)
混合三种背包问题
有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）
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][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
分组的背包问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态：f[k][v]表示前k组物品花费费用v能取得的最大权值
状态转移方程：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]}
以下来源于九章算法课件 -- jiuzhang.com
- 状态 State （灵感，创造力，存储小规模问题的结果) 何时用dp？
- 最优解/Maximum/Minimum
- Yes/No
- Count(*)
- 方程 Function
- 状态之间的联系，怎么通过小的状态，来求得大的状态
- 初始化 Intialization
- 最极限的小状态是什么, 起点
- 答案 Answer
- 最大的那个状态是什么，终点
题目类型1
利用滚动数组对空间的优化（从小朝大递推）
题目类型2
记忆化搜索 （从大朝小递推）什么时候用？
- 状态转移特别麻烦，不是顺序性。
- 初始化状态不是很容易找到。
题目类型3
区间类DP, 特点：
- 求一段区间的解max/min/count
- 转移方程通过区间更新
- 从大到小的更新
题目类型4
双序列动态规划
state: f[i][j]代表了第一个sequence的前i个数字/字符，配上第二个sequence的前j个...
- function: f[i][j] = 研究第i个和第j个的匹配关系
- initialize: f[i][0] 和 f[0][i]
- answer: f[n][m] min/max/数目/存在关系
- n = s1.length()
- m = s2.length()
题目类型5
背包类DP，特点：
- 用值作为DP维度
- DP过程就是填写矩阵
- 可以滚动数组优化
