DP常见考虑角度
状态表示
以0/1背包问题为例：
- 所求解问题用几维变量表示。
- 常见的两维: $ f_{i,j} $ 。
- 两个考虑角度：集合+属性
- 表示的集合是什么： 所有选法的集合。
- 条件：只从前 \(i\) 个物品里面选，总体积 \(\leqslant j\) 。
- 集合的属性是什么： 最大值、最小值、元素数量
- 表示的集合是什么： 所有选法的集合。
- \(f_{i,j}\) 表示：从前 \(i\) 个物品中选，所有选法集合里面，总体积 \(\leqslant j\) 的最大价值，答案所求即为 \(f_{N,V}\) 。
状态计算
- 对应集合的划分。
- 把当前集合划分成若干的更小的子集，使得每一个子集都可以由前面更小的集合算出来。
- 举例背包问题： 不包含物品 \(i\) or 包含物品 \(i\) 。
DP优化
- 对状态方程做等价变形。
DP时间复杂度
状态数量\(\times\)求每一个状态所花的时间。
背包问题
背包总体积为 \(V\) 。总共有 \(N\) 件物品，每个物品所占体积为 \(v_i\) ，价值为 \(w_i\)。
01背包
每件物品最多使用一次。
$$f_{i,j} = max\left (f_{i-1,j} ，f_{i-1,j-v_i} + w_i \right ) $$.
for (int i=1;i<=N;i++){
for (int j=1;j<=V;j++){
f[i][j]=f[i-1][j];
if (j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
空间复杂度降到一维，\(O \left( V \right)\)：
for (int i=1;i<=N;i++){
for (int j=V;j>=v[i];j--){
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
注意 \(f_j\)什么时候代表 \(f_{i,j}\) ， 什么时候降到 \(f_{i-1,j}\)。
完全背包
每件物品都有无限个。
$$f_{i,j} = max\left (f_{i-1,j} ，f_{i-1,j-k \times v_i} + k \times w_i \right ) ， k \times v_i \leqslant j$$.
for (int i=1;i<=N;i++){
for (int j=0;j<=V;j++){
for (int k=0;k*v[i]<=j;k++){
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
优化思路：
时间复杂度优化到二维，\(O \left( NV \right)\)：
\(
f_{i,j} = max\left (f_{i-1,j} ，f_{i-1,j-v_i} + w_i ， f_{i-1,j-2 \times v_i} + 2 \times w_i ,...f_{i-1,j-k \times v_i} + k \times w_i\right)
\)
\(
f_{i,j-v_i} = max\left ( \quad \quad f_{i-1,j-v_i} ，f_{i-1,j-2 \times v_i} + w_i ， f_{i-1,j-3 \times v_i} + 2 \times w_i ,...,f_{i-1,j-k \times v_i} + k-1 \times w_i\right)
\)
因此：
$$f_{i,j} = max\left (f_{i-1,j} ，f_{i,j-v_i}+w_i \right ) $$.
for (int i=1;i<=N;i++){
for (int j=1;j<=V;j++){
f[i][j]=f[i-1][j];
if (j>=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
}
空间复杂度降到一维，\(O \left( V \right)\)：
for (int i=1;i<=N;i++){
for (int j=v[i];j<=V;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
多重背包
每件物品最多使用 \(s_i\) 个。
$$f_{i,j} = max\left (f_{i-1,j} ，f_{i-1,j-k \times v_i} + k \times w_i \right ) ， k \leqslant s_i , k \times v_i \leqslant j$$.
for (int i=1;i<=N;i++){
for (int j=0;j<=V;j++){
for (int k=0;k*v[i]<=j && k<=s[i];k++){
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
多重背包问题的优化
二进制优化枚举\(0-s_i\)，时间复杂度降到 \(O \left( NVlogS \right)\)。
分组背包问题
有多组物品，每一组物品里面最多选一个。