DP(背包)
满足以下性质：
-
1.无后效性
-
如果给定某一阶段的性质，则在这一阶段以后过程的发展不受这阶段以前各段性质的影响，也就是说，到达一个状态的过程是怎么样的，不影响这个状态之后的状态
-
2.最优子结构
-
大问题的最优解可以由小问题的最优解推出，只考虑子问题在各种情况下的最优解
设计DP
转移方程
实现方式
背包DP
1. 01背包
f[i][j] = max(f[i - 1][j] , f[i - 1][j - w[i]] + v[i]) (j > w[i])
f[i % 2][j] = max(f[(i - 1) % 2][j] , f[(i - 1) % 2][j - w[i]] + v[i] (滚动数组优化空间))
for i = 1…n
for j = V…0
f[j] = max(f[j] , f[j - w[i]] + v[i])
2. 完全背包
3. 多重背包
-
可以对$c_i$进行二进制拆分，然后当01背包做，复杂度O(nmlogci)
-
更好的做法是直接用单调队列优化，复杂度O(nm)
-
对于m%$w_i$的每个剩余系分别更新其状态
-
以0为例,f[0] (+v[i]) → f[w[i]] (+v[i]) → f[2 * w[i]] (+v[i])
-
只有是同一剩余系的才更新状态
-
单调队列维护多重背包例题:宝物筛选
for(int i = 0;i < w;i++)
{
head=0,tail=-1;
k=(capacity-i)/w;
for(int j = 0;j <= k;j++)
{
while(head <= tail && dp[i + j * w] >= q[tail].val + j * v)
tail--;
q[++tail] = (node){j , dp[i + j * w] - j * v};
while(head <= tail && c < j - q[head].time)
head++;
dp[i + j * w] = max(dp[i + j * w],q[head].val + j * w);
}
}
}
}
二维费用背包
分组背包
f[k][j] = max(f[k - 1][j] , f[k - 1][j - w[i]] + v[i])
例题：
eg1: 质数和分解
-
即已知若干个质数，每个质数能使用无限次，问拼成n有多少种方案
-
设f[i][j]表示只使用前i个质数，拼出j的方案数
-
f[i][j] = f[i - 1][j] + f[i - 1][j - x] + f[i - 1][j - 2x] + ……，复杂度O(n^3)
-
考虑优化：
-
假设第i个质数为x，则转移方程变为 f[i][j] = f[i-1][j] + f[i][j - x]，复杂度O(n^2)
eg2: 飞扬的小鸟
-
完全背包
-
设dp[i][j]表示小鸟跳到第i列第j行的最少点击次数
-
初始状态：f[0][1~m]=0
-
最终状态：f[n][1~m]=inf
-
将管道设为inf，找第n列的最小值
-
f[i][j] = min(f[i - 1][j - k * xi] + k)(上升时)
-
考虑优化：f[i][j] = min(f[i - 1][j - x_i] + 1 , f[i][j - x_i + 1)
-
f[i][j] = min(f[i - 1][j + y_i] , f[i - 1][j - x_i] + 1 , f[i][j - x_i + 1)
-
先进行上升转移，再进行下降转移，因为优化后的上升包含一部分的转移，只有之后下降才保证上升下降不会同时出现
-
上升时转移后高度为min(i + x_i , m)
-
若填表时有发现val为inf的，管道数就是之前的管道数总和
eg3: 垃圾陷阱
-
dp[i][j]代表当前枚举到第i个垃圾，高度为j时的最长的剩余生命时间
-
f为维持生命的时间,t为垃圾掉落的时间
-
dp[i][j] = max(dp[i][j] , dp[i - 1][j] + f[i] - (t_i - t_{i-1}))(吃)
-
dp[i][j] = max(dp[i][j] , dp[i - 1][j - h_i] - (t_i - t_{i-1}))(堆)