【算法】基础DP

参考资料

背包九讲

一、线性DP

1. 如果现在在状态 i 下，它上一步可能的状态是什么。
2. 上一步不同的状态依赖于什么。

根据上面的分析，分析出状态和转移方程。注意：dp 不一定只有两维或者一维，一开始设计状态时先不考虑维度。如果空间超了的话考虑滚动数组等优化，或者再重新设计状态。

可以通过哪一个条件范围小来入手设计状态。

对于边界条件：一般是考虑第一个点的特殊情况，即 (dp_{[1]})。

二、背包问题

1. 01背包

模型总结：每个物品只能选一次。

思想

每件物品可以通过放或者不放来转移，所以它还依赖于之前使用的容量。设 (dp_{[i][j]}) 表示前 (i) 件物品用了 (j) 的容量的最大价值。不难得出：(dp_{[i][j]}=max(dp_{[i-1][j]},dp_{[i-1][j-v[i]]+w_[i]}))。

考虑优化维度，常用的方法是优化掉前 (i) 个物品的维度（对很多题目也同样适用）。设 (dp_{[j]}) 表示目前位置使用 (j) 的容量的最大价值。于是状态转移方程变成了：(dp_{[j]}=max(dp_{[j]},dp_{[j-v[i]]}+w_{[i]}))。

由于 (v_{[i]}ge 0)，所以 (j-v_{[i]}le j)，为了保证 (j-v_{[i]}) 一定是上一次 (i-1) 个物品的，所以我们循环 (j) 的时候要倒序循环。或者画出二维 DP 转移列表来理解。

代码：

for(int i=1;i<=n;i++) 	for(int j=m;j>=v[i];j--) 		dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 

2. 完全背包

模型总结：每个物品可以选无限次

思想

按照 01 背包的思想设计出初始状态：设 (dp_{[i][j]}) 表示前 (i) 件物品用了 (j) 的容量的最大价值。然后循环枚举选 (k) 个物品，仿照上面转移方程求出最大值。

继续考虑优化，依旧设 (dp_{[j]}) 表示目前位置使用 (j) 的容量的最大价值。但这次不能再循环 (k) 个物品了。我们返回去思考为什么 01 背包循环 (j) 要倒序循环，因为 01 背包只能选 1 个。那么如果它正序循环的话，(dp_{[j]}) 还有可能取到现在正在取的 (i) 个物品（因为 (dp_{j-v[i]}) 可能在这次循环中已经被更新过了），跟完全背包的模型相符。

代码

for(int i=1;i<=n;i++) 	for(int j=v[i];j<=m;j++) 		dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 

3. 多重背包

模型总结：每个物品有各自可选的最多次数 (k)。

思想

按照完全背包暴力的思想同样可以得到暴力解法。

时间复杂度超时的原因主要是由于循环了 (k) 这个维度，于是接下来需要优化这个维度。这里可以使用二进制优化，将循环枚举的 (k) 从 ([1,p]) （(p) 是最多选的个数）变为 (1,2,4...2^{k-1},p-2^k+1)（(k) 是满足 (p-2^k+1>0) 的最大整数）。

现在证明 ([1,p]) 的所有数都可以被写成上面转化后的数的和：

对于 (S_1=[0,(2^k-1)]) 这一区间的数：(2^x,2^{x-1}) 中间相差了一个 (2^{x-1})，如果 ([1,2^{x-1}-1]) 中的所有数都可以被写成上面的形式，那么 ([2^{x-1},2^x]) 中的所有数也可以满足条件，即 ([1,2^x]) 都会满足条件。于是 (x) 的值追根溯源到 (0)，此时显然 ([1,1]) 中的所有数都会满足条件，再根据上面的递推就可以证明出来了。

对于 (S_2=[2^k,p]) 这一区间的数：(p=(p-2^k+1)+2^k-1)。由于这一区间内都是连续的，所以所有数都可以被表示为 ((p-2^k+1)+x;(xin S1))。证明完毕。

代码

for(int i=1;i<=n;i++){ 	int maxi; 	if(v[i]==0) maxi=p[i]; 	else maxi=min(p[i],t/v[i]); 	for(int k=1;maxi>0;k<<=1){ 		k=min(k,maxi); 		maxi-=k; 		for(int j=t;j>=v[i]*k;j--) dp[j]=max(dp[j],dp[j-v[i]*k]+w[i]*k); 	} } 

4. 其他

混合背包：只需分类讨论上述情况即可。

二维背包费用（选一个物品有两个价值）：只需再多增一维按照上面来转移即可。有时另一种价值的表述方法也会变成“最多选 (x) 件物品”。

分组背包（每组里面最多选一件物品）：对每组的 (dp_{[j]}) 取最大即可。

依赖背包（有些物品必需先选另一种物品后才能选）：对于每一个没有依赖的背包分类讨论，只选它自己，选它自己+依赖1……等。

三、区间DP

对于有些一眼能看出来的区间DP题一般都是拆分类/合并类的题，典型的有：P1880 合并石子。但关键要看大区间内的答案能否可以通过小区间内的答案转移而来。

将在一段大区间内进行的DP，分解成小区间内进行的DP,大都需要以下几个条件：

1. 跨度（阶段）
2. 起点（状态）
3. 合并的位置（决策的位置）

比较典型的伪代码：
核心思路：先计算出小区间，再推出大区间，边界一般为区间长为 1 的时候

for 子区间长度 2 to n;    for 起点 1 to 终点不大于n        终点=起点+子区间长度-1        for 决策点 起点 to 终点-1           状态转移方程 

四、状压DP

对于有多种情况可以影响答案的时候，通常选择暴力开维度来存储信息。但有时会导致维度太多而爆空间，这时候我们要将形式相同的维度压缩成一维，这就是状压DP。

状压DP的一大重点便是位运算，而位运算又会引申出位操作。下面是几种常见位运算及位操作的意义：

一个二进制数位 &1 得到它本身。（& 表示两个数的相同位上，只有两个都为 (1)，最终的值才为 (1)。通常被看做两个集合的交集。）

一个二进制数位 ^1 则取反。（^ 表示两个数的相同位上，只有值不同，最终的值才为 (1)）

一个二进制数位 &0 则赋值为 (0)。

一个二进制数位 |1 则赋值为 (1)。（| 表示两个数的相同位上，只要有一个为 (1)，最终值就为 (1)）

(n>>k)&1 取出二进制下 (n) 的第 (k) 位 （从右往左）。

n&((1<<k)-1) 取出二进制下 (n) 的右 (k) 位。

n^(1<<k) 将二进制下 (n) 的第 (k) 位取反。

n|(1<<k) 将二进制下 (n) 的第 (k) 位赋值为 (1)。

n&(-(1<<k)) 将二进制下 (n) 的第 (k) 位赋值为 (0)。