线性dp¶
经典问题¶
最长上升子序列¶
-
- 普通dp O(\(n^2\)),二分版本O(\(nlgn\))
-
- 需要用二分方法
- 即找到第一个满足\(d[i-1]<nums[j]<d[i]\)（即让每个位置尽可能小）
-
普通版本通用性强，但效率较低
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}
- 673. 最长递增子序列的个数
- 354. 俄罗斯套娃信封问题
- 二维
- 960. 删列造序 III
- 自定义比较
- （难）1691. 堆叠长方体的最大高度
- 双排列，即使存在不能堆叠情况，还需要具体检查，可以保证dp便历的顺序性（从小到大）
- P3287 方伯伯的玉米田
- 使用树状数组维护，每次一定是把[L,n]++因为让右面更大不会有坏处
- dp[i][j]表示做过j次操作，每次起点不超过i（后面加对前面的LIS没有意义），且以i为子序列结尾的LIS长度
dp[i][j]=max{dp[x][y]+1}x<i,y<=j,a[x]+y<=a[i]+j
- 最长不下降子序列
- 结合多个树状数组，可以使用树状数组计算上升序列，还便于查询
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,ans,val[N],L[N],R[N];
vector<int> vec;
struct BIT
{
int C[N];
inline void add(int x,int y){for(;x<=n;x+=x&-x) C[x]=max(C[x],y);}
inline int query(int x)
{
int ans=0;
for(;x;x-=x&-x) ans=max(ans,C[x]);
return ans;
}
}le,re,s;
int main()
{
scanf("%d%d",&n,&k);
val[0]=1;val[n+1]=n+1;//添加哨兵位，避免额外的讨论
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
for(int i=1;i<=n;i++) vec.push_back(val[i]);
//离散化
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i=1;i<=n;i++) val[i]=lower_bound(vec.begin(),vec.end(),val[i])-vec.begin()+1;
//正反分别计算以其为开头/结尾的最长序列
for(int i=1;i<=n;i++)
{
L[i]=le.query(val[i])+1;//小于等于其的元素的最大长度加一（可以构成的新序列的最大长度）
le.add(val[i],L[i]);
}
for(int i=n;i>=1;i--)//反着来看
{
R[i]=re.query(n-val[i]+1)+1;
re.add(n-val[i]+1,R[i]);
}
for(int i=k+1;i<=n+1;i++)//假设
{
s.add(val[i-k-1],L[i-k-1]);//连续k个之前能做到的最大长度，用树状数组维护
ans=max(ans,s.query(val[i])+k+R[i]);//枚举右启点，树状数组维护的左面长度+k+右面长度
}
printf("%d",ans);
return 0;
}
最长公共子序列¶
-
\(O(n^2)\)
-
\(x[i]==y[i]\) \(dp[i][j]=1+dp[i-1][j-1]\)
-
\(x[i]!=y[i]\) \(dp[i][j]=max(dp[i-1][j],dp[i][j-1])\)
-
如果两个串是相同元素的不同排列，那么可以使用二分版本最长上升子序列在 \(O(nlogn)\) 时间解决
双串问题¶
例题¶
- 双向，路径往返，不好分别处理，就同时处理\(dp[i][j][k]\)表示到i处去时处于状态j回来处于k的状态
- 本体存储去时加油之后，回来时加油之前，确保加油站是否使用可以直接决定
[[区间dp]][[区间dp2]]¶
- 减治型：dp[i][j] 仅与常数个更小 规模子问题有关，不需要枚举分割点然后两边分别求解。一般是与 dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1] 有关。
- 分治型：dp[i][j] 仅与 O(n) 个更小规模子问题有关，需要枚举分割点然后两边分别求解。一般是枚举 [i, j] 的分割点，将区间分为 [i, k] 和 [k+1, j]， 对每个 k 分别求解（下面公式的 f），再汇总。
- 核心：把较长的区间转化为较短的区间进行转移
- 通常可以枚举起点和区间长度进行计算
例题¶
-
较为复杂，两次区间dp
- 先计算空白串转化为B串需要的次数
- 再计算A到B需要的次数
-
```c++ #include
using namespace std; char A[105],B[105]; int dp[105][105]; const int INF = 0x3f3f3f3f; int main() { while(~scanf("%s%s", A+1, B+1)){
int n = strlen(A+1); //输入A, B for(int i=1;i<=n;i++) dp[i][i]=1; //初始化 //先从空白串转换到B for(int len=2; len<=n; len++) for(int i=1; i<=n-len+1; i++){ int j = i + len-1; dp[i][j] = INF; if(B[i] == B[j]) //区间[i, j]两端的字符相同B[i] = B[j] dp[i][j] = dp[i+1][j]; //或者 = dp[i][j-1]) else //区间[i, j]两端的字符不同B[i] ≠ B[j] for(int k=i; k<j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
} //下面从A转换到B for(int j=1; j<=n; ++j){ if(A[j] == B[j]) dp[1][j] = dp[1][j-1]; //字符相同不用转 else for(int k=1; k<j; ++k) dp[1][j] = min(dp[1][j], dp[1][k] + dp[k+1][j]); } printf("%d\n",dp[1][n]); } return 0; }```
-
dp[i][j]=dp[i+1][i+k-1]+D[i]*(k-1)+dp[i+k][j]+k*(sum[j]-sum[i+k-1]) -
对于每个区间都是假设排在最前面，如果不是放在区间最前面要加上怒气值
-
对于一个字符串只会有两种操作：拼接形成该字符串；对字符串进行压缩
-
对于一个区间，最后一个被关闭的路灯一定是位于左端点或右端点
- dp[i][j][]就是表示区间内的灯已经被关闭了（也可以说其他灯没有被关闭），且最终位置在左/右
- 那么i-1或j+1就是下一个要关闭的等，新产生的代价，就是从i-j关闭完成转移到新点关灯过程中消耗的电量
- 此外此题限定出发点，要将其他位置赋值为很大，即从起点向wai
二维区间dp¶
-
最小代价把图涂成白色（代价为区域长、宽的较大值）
-
用x1x2y1y2四维dp表示，枚举分割（如一个水平轴）复杂度
O(n^5) -
两个方向
dp[x1][][x2][]=min(~,dp[x1][][k][]+dp[k+1][][x2][])dp[][y1][][y2]=min(~,dp[][y1][][k]+dp[][k+1][][y2])
-
```c++ #include
using namespace std; #define N 55 int dp[N][N][N][N]; char mp[N][N]; //方格图 int main(){ int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>mp[i][j]; //初始化dp for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]=='.') dp[i][j][i][j]=0; //白格不用涂 else dp[i][j][i][j]=1; //黑格(i,j)涂成白色需1次
for(int lenx=1;lenx<=n;lenx++) //len从1开始，不是2。因为有x和y两个方向 for(int leny=1;leny<=n;leny++)
for(int x1=1;x1<=n-lenx+1;x1++) for(int y1=1;y1<=n-leny+1;y1++){
int x2 = x1+lenx-1; //x1：x轴起点；x2：x轴终点 int y2 = y1+leny-1; //y1：y轴起点；y2：y轴终点 if(x1==x2 && y1==y2) continue; //lenx=1且leny=1的情况
dp[x1][y1][x2][y2] = max(abs(x1-x2),abs(y1-y2)) + 1; //初始值 for(int k=x1;k<x2;k++) //枚举x方向，y不变。区间[x1,k]+[k+1,x2] dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], dp[x1][y1][k][y2]+dp[k+1][y1][x2][y2]);
for(int k=y1;k<y2;k++) //枚举y方向，x不变。区间[y1,k]+[k+1,y2] dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], dp[x1][y1][x2][k]+dp[x1][k+1][x2][y2]);
}
cout << dp[1][1][n][n]; }```
¶
棋盘dp¶
例题¶
- 1277. 统计全为 1 的正方形子矩阵
- 状态转移难想
- 688. 骑士在棋盘上的概率
- 概率问题
- 1937. 扣分后的最大得分
- 需要优化
- 174. 地下城游戏
- 568. 最大休假天数
- P1004 方格取数
- 有趣的棋盘dp，同时枚举两条路线的动态规划
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
for(int l = 1; l <= n; l++){
//枚举可能的4种来源
dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])) + a[i][j] + a[k][l];
//落在相同点，防止重复取数
if(i == k && j == l){
dp[i][j][k][l] -= a[i][j];
}
}
}
}
}
树形dp¶
思想¶
- 树形 DP：就是在树形结构上进行推导的动态规划问题。树形 DP 一般以当前所在的深度为阶段，具体在该深度的哪个点为附加状态，可以用节点编号作状态表示。除此之外可能有别的附加状态。
- 本质上是dfs搜索，用回溯进行，并没有dp数组记录内容。
例题¶
- 333. 最大 BST 子树
- 968. 监控二叉树
- 1273. 删除树节点
- 6294. 最大价值和与最小价值和的差值
- dp维护含叶节点和不含的最长路径，为了防止路径重合，可以在搜索过程中跟新最大值
- 维护已得到的子树的最大值，与新搜索得到的值进行计算，可以保证两条路径不会重合
- 834. 树中距离之和
- 难，多次dfs
- 1569. 将子数组重新排序得到同一个二叉查找树的方案数
- 很难，复杂
- 通过递推方式求解组合数可以避免除法，便于取余数
图上dp¶
经典问题¶
例题¶
概率&期望dp¶
- 常用全概率公式&全期望公式（条件概率，条件期望）
例题¶
- 剑指 Offer 60. n个骰子的点数¶
背包问题¶
概述¶
有n种物品，物品i体积为\(v_i\)，价值为\(w_i\)，体积总限制为v，目的是使总价值w最大。
基本概念¶
01背包¶
01表示每种物品都只有一个，只能选或不选。
用dp[i][j]表示考虑编号0-i的物品，在占用空间为j的情况下的最大价值。那么有状态转移方程：
dp[i][j]=dp[i-1][j]//不选择i
` dp[i][j]=dp[i-1][j-v[i]]+w[j]//选择i
dp[j]=max(dp[j],dp[j-v[j]]+w[j])
- 一种特殊情况：要求背包必须放满，那么就不是所有情况都能取到了，初始化时不再初始化为0，而用-1表示不可取，dp[0][0]仍为0，在状态转移更新dp[i][j]时，只有上一项不为-1才能选择。
完全背包¶
每种物品都有无限个。 状态转移方程：
dp[i][j]=dp[i-1][j]//不选择i
dp[i][j]=dp[i][j-v[i]]+w[j]//选择i
dp[j]=max(dp[j],dp[j-v[j]]+w[j])
组合背包¶
背包中的物品要考虑顺序。
分组背包(多维背包)¶
- 把物品分成许多组，每组背包只能选择一个物品
- 多一层循环，处理每组内的元素
- \(dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i][k]]+w[i][k])\)
- 使用滚动数组可以省略i但是j要倒序遍历
- k应该在最内层循环
for (int i = 1; i <= n; ++i)
for (int j = m; j >= 0; --j) //对于01分组背包，j依然需要倒序（否则出现一个物品使用多次）
for (int k = 0; k < s[i]; ++k)//k必须从小到大遍历（否则出现选择同一个组内的多个物品）
if (j >= v[i][k])
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
- 对分组背包的优化（可以随着组的遍历逐渐增大啊背包的容量，每次增加组中最大的元素）
//最外层遍历组，逐渐增大容量
sz[u]+=sz[v];
for(int j=min(m,sz[u]);j>=0;--j){ //遍历容量
if(f[u][j]!=-1) //在DP前应先加上当前子节点的子树纯白色的情况，这是下面也倒序枚举的前提
f[u][j]+=f[v][0]+(ll)sz[v]*(n-m-sz[v])*e[i].w;
for(int k=min(j,sz[v]);k;--k){ //
if(f[u][j-k]==-1)continue;
ll val=(ll)(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w; //当前情况下连接子节点的边的贡献
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+val);
}
}
多重背包¶
每种物品有\(c_i\)个
- 朴素算法，展开为01背包，第i个物品有min(c[i],v/v[i])个
- 也可以直接计算（ijk三层循环）\(dp[i][j]=max{dp[i-1][j],dp[i-1][j-k*c[i]]+k*w[i]} (1<=k<=min(m[i],j/c[i]))\)
- 复杂度\(O(C\sum{m})\)
- 大部分情况朴素方法会超时，需要优化
二进制优化¶
-
复杂度\(O(C\sum{logm})\)
-
按2分解，将\(c_i\)用2的多项式分解，如下拆分：(\(w_i\),\(v_i\)),(2\(w_i\),2\(v_i\))……
- 最后一个数可能不是2的幂而是剩下的余数
- 并不是按照二进制位的01直接计算，而是按照2的幂从小到大，直至大于
- 如25可以拆分为1 2 4 8 10（剩余的量）
单调队列优化¶
-
复杂度\(O(C N)\)
-
状态转移$dp[j] = max(dp[j] , dp[j - v] + w , dp[j - 2 * v] + 2 * w , ..... , dp[j - s * v] + s * w) $
-
j只和前面间隔v的dp数组相关，也就是说j、j - v、 j - 2v ... j - sv都是同余的，我们将同余的归为一组，而dp[0...V]中共有v组。既然如此，可以对dp方程稍作修改，令j范围是(0 < j < v)，j就意味着同余的余数。
-
-
这样，每个max函数内的形式就统一了，形式统一的好处就是dp[j + 2v]就是前2项的最大值，当求第三项时，不需要全局比较，只需要和第二项比较即可。此时对求dp[j],dp[j + v],dp[j + 2v],...,dp[j + sv]维护一个单调队列，由于单调队列队首始终存放最大值，当计算dp[j +kv]时，只需要比较dp[j +(k - 1)v] - (k - 1)w 和 dp[j + kv] - kw即可。因为dp[j +(k - 1)v] - (k - 1)w 已经是前k - 1项最大值了。
-
为什么需要单调队列：每种物品的数目有上限（如背包可能容量为20，物体空间为3，但只有3个），因此并不是前面所有项的最大值，而是至多S（数目）项！这个问题也就相当于计算滑动窗口的最大值，自然使用单调队列
- 如j与j-ci、j-2ci、j-3ci相关，那么j+ci就与j、j-ci、j-2ci相关
-
状态转移（j=b+yci）\(dp[b+yc_i]=max(dp[b+xc_i]-xv_i+yw_i)(y-min(m_i,y)<=x<=y)\)
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,C;
int dp[N],q[N],num[N];
int w,c,m; //物品的价值w、体积c、数量m
int main(){
cin >> n >> C; //物品数量n，背包容量W
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
cin>>w>>c>>m; //物品i的价值w、体积c、数量m
if(m>C/c) m = C/c; //计算 min{m, j/c}(再多的物品也装不下)
for(int b=0;b<c;b++){ //按余数b进行循环
int head=1, tail=1;
for(int y=0;y<=(C-b)/c;y++){ //y = j/c（这两个循环加一起也就ci*C/ci=C）
int tmp = dp[b+y*c]-y*w; //用队列处理tmp = dp[b + xc] - xw
while(head<tail && q[tail-1]<=tmp) tail--;
q[tail] = tmp;
num[tail++] = y;
while(head<tail && y-num[head]>m) head++;
//约束条件y-min(mi,y)≤x≤y
dp[b+y*c] = max(dp[b+y*c],q[head]+y*w); //计算新的dp[]
}
}
}
cout << dp[C] << endl;
return 0;
}
常见问题¶
- 最值问题
- 存在问题
- 组合问题（求满足条件的所有排列组合）
- 注意：背包问题通常要求选择物品的量不能超过背包容量，但是如果是要求必须装满，则需要对除了0等可以直接实现的项赋值-1，每次只能从不是-1的项转移得到
模板¶
- 背包问题通用模板
// 0-1背包问题母代码(二维) void bags() { vector<int> weight = {1, 3, 4}; //各个物品的重量 vector<int> value = {15, 20, 30}; //对应的价值 int bagWeight = 4; //背包最大能放下多少重的物品 // 二维数组：状态定义:dp[i][j]表示从0-i个物品中选择不超过j重量的物品的最大价值 vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0)); // 初始化:第一列都是0，第一行表示只选取0号物品最大价值 for (int j = bagWeight; j >= weight[0]; j--) dp[0][j] = dp[0][j - weight[0]] + value[0]; // weight数组的大小 就是物品个数 for (int i = 1; i < weight.size(); i++) // 遍历物品(第0个物品已经初始化) { for (int j = 0; j <= bagWeight; j++) // 遍历背包容量 { if (j < weight[i]) //背包容量已经不足以拿第i个物品了 dp[i][j] = dp[i - 1][j]; //最大价值就是拿第i-1个物品的最大价值 //背包容量足够拿第i个物品,可拿可不拿：拿了最大价值是前i-1个物品扣除第i个物品的 重量的最大价值加上i个物品的价值 //不拿就是前i-1个物品的最大价值,两者进行比较取较大的 else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } cout << dp[weight.size() - 1][bagWeight] << endl; } - 空间优化版本
void test_1_wei_bag_problem() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; // 初始化 vector<int> dp(bagWeight + 1, 0); for (int i = 0; i < weight.size(); i++) { // 遍历物品 for (int j = bagWeight; j >= weight[i]; j--) //j<weight[i]后会直接复制，因此可以跳过 { // 遍历背包容量(一定要逆序) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //不取或者取第i个 } } cout << dp[bagWeight] << endl; } - 分类模板（空间优化版本）
- 背包分类
- 0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
- 完全背包：外循环nums,内循环target,target正序且target>=nums[i];
- 组合背包：外循环target,内循环nums,target正序且target>=nums[i];
- 分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板
- 问题分类
- 最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
- 存在问题(bool)：dp[i]=dp[i]||dp[i-num];
- 组合问题(计数)：dp[i]+=dp[i-num];
- 因为考虑排列顺序，这样才可以得到全排列；如果不考虑顺序，那就变成了普通背包问题，不需要调换顺序。
例题（特殊）¶
- 474.一和零(多维背包)
-
多维也可以通过倒序优化空间复杂度！
-
转化为两堆，尽可能接近，不易想到。
-
计数问题，区分是否区别顺序
- 排列377.组合总和4
- 本题特殊之处要求盈利大于等于一个数，这与通常的体积限制是相反的
- 方法一：
仅初始化为dp[0][0]=1，那么dp表示利润至少为minProfit时恰好使用的工人
int sum = 0; for (int j = 0; j <= n; j++) { sum = (sum + dp[len][j][minProfit]) % MOD; } return sum; - 方法二：
初始化为dp[i][0]=0，dp表示利润至少为minProfit时可以使用的工人（大于等于恰好）
直接返回
return dp[n][minProfit] -
此外状态转移方程稍有不同，还要计算超出minProfit范围的
dp[j][k] = (dp[j][k] + dp[j - members][max(0, k - earn)]) -
- 二维组合背包
-
- 用01背包思想判断一个组合是否存在
-
- 嵌套背包问题
-
- 倍增思想，dp[i][j]表示以 j 为左端点可以合并为 i 的区间的右端点
-
- 普通的 01 背包但是 w 很大（但是 v 正常）
- 可以反过来想，传统的背包是前 i 个元素重量至多为 w 的最大 v；可以转化为前 i 个元素价值为 v 时的最小 w
状态压缩动态规划¶
- 位运算
- 通常处理NPC问题，如子集问题（2n）,排列问题（n!）
常用位运算操作¶
- 枚举A的子集
for(subset = (A - 1) & A; subset != A; subset = (subset - 1) & A)
{
...
}
/*
如A=1011,遍历如下
1010&1011=1010,
1001&1011=1001;
1000&1011=1000;
0111&1011=0011;
0010&1011=0010;
0001&1011=0001;
0000&1011=0000;
1111&1011=1011;
*/
- 枚举全集的子集
for(i = 0; i <= (1 << n) - 1; ++i)//如n=4，那么10000-1=1111，对0000-1111枚举
{
...
}
应用¶
最短哈密尔顿回路¶
- 图上遍历二维，分别记录经过的点以及正处在的点
dp[s][i] = dp[s | (1 << j)][j] + w[i][j]; //从 i 点转移到 j 点
- 从s删除新加的点，并从之前已经有的点中选择一个作为末尾
if( ((S>>j) & 1) && ((S^(1<<j)) >> k & 1) )
dp[S][j] = min(dp[S][j],dp[S^(1<<j)][k] + dist[k][j]);
- \(O(n^22^n)\)
- P1433 吃奶酪
- P3694 邦邦的大合唱站队
- 在使用状态压缩动态规划（DP）解决最短哈密尔顿回路问题时，通常需要存储当前所在的点，因为这可以帮助我们跟踪已经访问的节点和当前的路径状态。
- 如果问题要求从一个特定的起点出发，经过所有节点一次且仅一次，然后回到起点，那么存储当前所在的点通常是必要的。但是，在一些问题中，可能只需要计算最短路径或最小代价，而不需要考虑哈密尔顿回路的约束，那么可能可以省略存储当前所在的点，只关注节点的访问状态和路径长度。（dp数组以及枚举循环都可以减少一行）
间隔分布¶
-
有时需要维护前面好多行的信息，表面上复杂度可能很高，但是由于大量不和放的情况会被提早剪枝，实际复杂度是可以接受的
-
c++ int maxStudents(vector<vector<char>>& seats) { int ans=0; vector<vector<int>>dp(seats.size(),vector<int>(1<<seats[0].size(),-1));//行数，一行上学生选座状态 for(int i=0;i<(1<<seats[0].size());i++) { bool badseat=0; for(int j=0;j<seats[0].size();j++) { if((i&(1<<j))&&seats[0][j]=='#')//是否有学生坐在了坏的座位上 { badseat=1; break; } } if(badseat||(i&(i<<1)))//非常巧妙，通过左移来判断冲突 continue; dp[0][i]=__builtin_popcount(i); } for(int i=1;i<seats.size();i++) { for(int j=0;j<(1<<seats[0].size());j++)//枚举本行 { bool badseat=0; for(int k=0;k<seats[0].size();k++) { if((j&(1<<k))&&seats[i][k]=='#') { badseat=1; break; } } if(badseat||(j&(j<<1))) continue; for(int k=0;k<(1<<seats[0].size());k++)//枚举上一行，取最大值 { if(dp[i-1][k]==-1||j&(k<<1)) continue; dp[i][j]=max(dp[i][j],dp[i-1][k]+__builtin_popcount(j)); } } } for(int i=0;i<(1<<seats[0].size());i++) ans=max(ans,dp[seats.size()-1][i]); return ans; } }; -
排兵布阵（hdu4539）
-
在一个棋盘上有一些点，部分点不能放置兵种，要求放置的兵种间的曼哈顿距离不得为2，问棋盘上可以放的最大数目
-
需要记录前两行的排列情况，dp[i][j][k]表示到第i行时可以放置的最大数目（j是第i行的排列，k是第i-1行）
-
```c++ #include
using namespace std; int mp[105][12]; //地图 int dp[105][200][200]; int n,m; int sta[200]; //预计算一行的合法情况。m = 10时，只有169种合法情况（存储所有可能的排列方式，这样可以用一个数字表示一种排列） int init_line(int n){ //预计算出一行的合法情况 int M = 0; for(int i = 0; i < n; i ++) if((i&(i>>2))==0 && (i&(i<<2))==0)//左右间隔2的位置没人，就是合法的 sta[M++] = i; return M; //返回合法情况有多少种 } int count_line(int i, int x){ //计算第i行的士兵数量 int sum = 0; for(int j=m-1; j>=0; j--) { //x是预计算过的合法安排 if(x&1) sum += mp[i][j]; //把x与地形匹配 x >>= 1; } return sum; } int main(){ while(~scanf("%d%d",&n,&m)) { int M = init_line(1<<m); //预计算一行的合法情况，有M种 for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) scanf("%d",&mp[i][j]); //输入地图 int ans = 0; memset(dp, 0, sizeof(dp)); for(int i = 0; i < n; i ++) //第i行 for(int j = 0; j < M; j ++) //枚举第i行的合法安排 for(int k = 0; k < M; k ++) { //枚举第i-1行的合法安排
if(i == 0) { //计算第1行（无需检查冲突） dp[i][j][k] = count_line(i, sta[j]); ans = max(ans, dp[i][j][k]); continue; } if((sta[j]&(sta[k]>>1)) || (sta[j]&(sta[k]<<1)))
continue; //第i行和第i-1行冲突 int tmp = 0; for(int p = 0; p < M; p ++){ //枚举第i-2行合法状态 if((sta[p]&(sta[k]>>1)) || (sta[p]&(sta[k]<<1))) continue;
//第i-1行和第i-2行冲突 if(sta[j]&sta[p]) continue; //第i行和第i-2行冲突 tmp = max(tmp, dp[i-1][k][p]); //从i-1递推到i } dp[i][j][k] = tmp + count_line(i, sta[j]); //加上第i行的士兵数量 ans = max(ans, dp[i][j][k]); } printf("%d\n",ans); } return 0; }```
-
由于只和前面固定数目项相关，可以使用滚动数组优化
- P5005 中国象棋 - 摆上马)
- 非常好的判断：
i&(~i>>1)&(j>>2)：左边没马且左上有马。
三进制状态压缩¶
-
最短哈密尔顿问题升级（要求每个节点至少被访问一次，但最多可以访问2次）
-
每个节点的访问状况都有012三种，因此状态压缩需要使用三进制
- 可以使用一个预处理转换数组（三进制打表）
-
比如用trp[i][j]表示压缩后值为i的路径上j城市的访问状况（类似使用位运算获取二进制的一位）
-
```c++ #include
const int INF = 0x3f3f3f3f; using namespace std; int n,m; int bit[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049}; //三进制每一位的权值。与二进制的0, 1, 2, 4, 8...对照理解 int tri[60000][11]; int dp[11][60000];//当前城市+访问状况
int graph[11][11]; //存图 void make_trb(){ //初始化，求所有可能的路径 for(int i=0;i<59050;++i){ //共3^10 = 59050种路径状态 int t=i; for(int j=1; j<=10; ++j){ tri[i][j]=t%3; t/=3; } } } int comp_dp(){
int ans = INF; memset(dp, INF, sizeof(dp)); for(int j=0;j<=n;j++) dp[j][bit[j]]=0; //初始化：从第j个城市出发，只访问j，费用为0 for(int i=0;i<bit[n+1];i++){ //遍历所有路径，每个i是一个路径 int flag=1; //所有的城市都遍历过1次以上 for(int j=1;j<=n;j++){ //遍历城市，以j为起点 if(tri[i][j] == 0){ //是否有一个城市访问次数是0（找一个已经被访问过可以删除进行转移的点） flag=0; //还没有经过所有点 continue; } for(int k=1; k<=n; k++){ //遍历路径i-j的所有城市 int l=i-bit[j]; //l:从路径i中去掉第j个城市 dp[j][i]=min(dp[j][i],dp[k][l]+graph[k][j]);
} } if(flag) //找最小费用 for(int j=1; j<=n; j++) ans = min(ans,dp[j][i]); //路径i上，最小的总费用 } return ans; } int main(){ make_trb(); while(cin>>n>>m){ memset(graph,INF,sizeof(graph)); while(m--){ int a,b,c; cin>>a>>b>>c; if(c<graph[a][b]) graph[a][b]=graph[b][a]=c; } int ans = comp_dp(); if(ans==INF) cout<<"-1"<<endl; else cout<<ans<<endl; } return 0; }
```
例题¶
-
- NPC
-
- 标准图上状态压缩问题（<已经选择的点，最后选择的点>）
-
c++ int countArrangement(int n) { vector<int>dp(1<<n,0); dp[0]=1; for(int mask=1;mask<(1<<n);mask++)//从小遍历 { int num=__builtin_popcount(mask);//计数1 for(int i=0;i<n;i++) { if(mask&(1<<i)&&(num%(i+1)==0||(i+1)%num==0)) dp[mask]+=dp[mask^(1<<i)];//比mask小，已经遍历过了 } } return dp[(1<<n)-1]; } -
只能动态规划，拓扑排序贪心不可行
-
poj2411
- 只考虑填入横向方块，第i列的填入只收到i-1列影响，使用状态压缩维护填入状态，只要保证上下相邻之间的距离为偶数就保证是合法的方案
- 第
i - 1行的状态k能转移到第i行的状态j，当且仅当j & k == 0， 即第i列和第i - 1列的每一行都没有连续两个横向棋子重叠放置st[j | k] == true i - 1即第i列和第i - 1列合并以后（要合并是因为第i列和第i - 1列都是两个空格子才行，一列有竖棋子的上半部分一列没有是不算的）的状态没有出现连续空格子为奇数个
计数问题¶
方法¶
-
找到组合数公式，然后用 DP 的方式或者用含阶乘的公式求组合数
-
组合数常用计算方法
分子分母都刚好为m项，转化为分数相乘可以避免溢出
for (int x = n-m+1, y = 1; y <= m; ++x, ++y) {
ans *= x / y;
}
- 找到递归关系，然后以 DP 的方式求这个递推关系，如果是线性递推关系，可以用矩阵快速幂加速
- 如果可以直接找到通项，就不需要递推了
- 矩阵快速幂：
例题¶
- （特殊）790. 多米诺和托米诺平铺
-
状态转移比较难想
-
假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，所以可得G(n) = G(0)G(n-1)+G(1)(n-2)+...+G(n-1)*G(0)
-
卡特兰数
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
dp[i]+=dp[j-1]*dp[i-j];
}
矩阵快速幂¶
概念¶
- 动态规划主要用于解决最优化问题和技术问题，矩阵快速幂主要用于解决计数问题，可以将时间复杂度从O(N)降低为O(logN)
- 矩阵快速幂主要用于线性的递推型计数问题，以及一些动态规划中状态转移方程是线性递推关系的时候。有一些计数问题，通过对 n 比较小的情况进行手动推导，发现规律，可以猜想出递推关系。如果这个递推关系是线性，那么它可以转换成矩阵求幂问题，进而可以用矩阵快速幂加速。
- 思想：求\(A^n\)时，先不求\(A^n\)，而是求\(A^{n/2}\)，然后先不求\(A^{n/2}\)，而是求\(A^{n/4}\)...
-
如何将线性关系转化为矩阵：
-
例题
模板¶
public:
vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
vector<vector<long long>> c(2, vector<long long>(2));//矩阵乘法
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
vector<vector<long long>> ret = {{1, 0}, {0, 1}};//创建一个单位矩阵，方便直接用矩阵乘法计算
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
int climbStairs(int n) {
vector<vector<long long>> ret = {{1, 1}, {1, 0}};//系数矩阵
vector<vector<long long>> res = matrixPow(ret, n);//求得系数矩阵n次幂,这个n与矩阵维数有关（也就是递推的初态），为：n+1-维数
return res[0][0];//这里要根据实际关系式从系数矩阵n次幂再乘以基础情况得到结果
}
例题¶
数位动态规划¶
概念¶
-
数位 DP 主要解决的问题: 在一段区间 [L, R] 上
-
满足某些条件的数字个数
-
将x∈[L,R] 代到一个函数 f(x) 中，一个数字 x 的 f(x) 值为一次贡献的量，求总的贡献
-
时间复杂度一般是 \(log_{10}L\)
-
枚举策略：对于区间 [L, R] 上的问题，首先变成解决前缀 [0, N] 的问题，[0, N] 上的问题解决后，求一次 [0, R] 和 [0, L- 1] 就可以得到原问题的解了。例如 N = 2357（需要两次做差时别忘了第一次调用后对arr数组复原）
-
memset(&dp,-1,sizeof(dp)); -
首先位数的范围是 3 ~ 0，第 3 位为 2，第 2 位为 3，第 1 位为 5，第 0 位为 7。
-
如果当前为枚举的数字因高位顶到了上界而被限制，则当前位的数字枚举也要分类：顶到上界，未顶到上界，这两种对低位的枚举影响不一样
-
当高位未顶到上界（可能是未被限制，也可能是被限制了但是选的数未顶到上界），则低位的数字无限制，可选 0 ~ 9。只有前面的所有位都顶到了上线，那么这一位才是有限制的，并且这一位顶到上限时下一位才是被限制的。
-
当高位顶到了上界，则低位的数字 被限制 且要分类：顶到上界和未顶到上界。
-
比如当前为是第 2 位，如果它的高位第 3 位是 0、1，则当前第 2 位的选择范围是 0 ~ 9 ；而当第 3 位为 2，第 2 为的选择范围就变成 0 ~ 3 。
-
dp[pos][lim]，pos 为当前的数位 N-1 ~ 0 ，lim 表示是否顶到上界 -
c++ dp[pos][0] = 10 * dp[pos - 1][0] dp[pos][1] = digits[i] * dp[pos - 1][0] + dp[pos - 1][1]
-
模板¶
- isLimit 表示当前是否受到了 n 的约束。若为真，则第i 位填入的数字至多为 s[i]，否则至多为 9。例如n=234，如果前面填了 23，那么最后一位至多填 4；如果前面填的不是 23，那么最后一位至多填 9。如果在受到约束的情况下填了 s[i*]，那么后续填入的数字仍会受到 n 的约束。
- isNum 表示 i 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；若为真，则必须填数字，且要填入的数字从 0 开始。这样我们可以控制构造出的是一位数/两位数/三位数等等。对于本题而言。
- mask 表示前面选过的数字集合，换句话说，第 i位要选的数字不能在 mask 中。（根据题目选择具体的标志含义）
class Solution {
public:
int arr[10][1024][2][2];//dp数组//可以额外添加维数表示是否满足某一性质
//含义：从第i位开始，在islimit,isnum条件下可能的合法方案数
int countSpecialNumbers(int n) {
string s=to_string(n);//转化为字符串bian'yu
return dp(0,0,true,false,s);
}
int dp(int i,int mark,bool islimit,bool isnum, string &n)//mark用了状态压缩储存
{
if(i==n.size())//结束条件
return isnum[i]&&isre;//isnum=0意味着没有取过数，自然方法数为0,isre表示满足题目指定的某种性质
if(arr[i][mark][islimit][isnum]!=0)//记忆化
return arr[i][mark][islimit][isnum];
int sum=0;
if(!isnum)//本位之前没有去数，那没本位可以继续不取数
sum=dp(i+1,mark,false,false,n);
int up=0;
if(islimit)//本位是否受限
up=n[i]-'0';
else
up=9;
for(int j=1-int(isnum);j<=up;j++)//本位填入数字方法数
{
if(((mark>>j)&1)==0)//j没有使用过
sum+=dp(i+1,mark|(1<<j),islimit&&j==up,true,n);
}
arr[i][mark][islimit][isnum]=sum;
return sum;
}
};
例题¶
- 902. 最大为 N 的数字组合
- 1067. 范围内的数字计数
- 前缀和做差
- 记录出现次数
class Solution {
public:
int arr[10][2][2][10];
int digitsCount(int d, int low, int high) {
int num1=dp(0,true,false,0,to_string(high),d);
for(int i=0;i<10;i++)//记忆数组复位
{
for(int j=0;j<2;j++)
{
for(int l=0;l<2;l++)
{
for(int k=0;k<10;k++)
arr[i][j][l][k]=0;
}
}
}//前缀差
return num1-dp(0,true,false,0,to_string(low-1),d);
}
int dp(int i,bool islimit,bool isnum,int isre,string n,int d)//isre记录到第i位之前d出现的数目
{
if(i==n.size())
return isre;
if(arr[i][islimit][isnum][isre]!=0)
return arr[i][islimit][isnum][isre];
int sum=0;
if(!isnum)
sum=dp(i+1,false,false,false,n,d);
int up=0;
if(islimit)
up=n[i]-'0';
else
up=9;
for(int j=1-isnum;j<=up;j++)
{
if(j==d)
sum+=dp(i+1,islimit&&j==up,true,isre+1,n,d);
else
sum+=dp(i+1,islimit&&j==up,true,isre,n,d);
}
arr[i][islimit][isnum][isre]=sum;
return sum;
}
};
- 1012. 至少有 1 位重复的数字
- 额外参数isre
- 1088. 易混淆数
- 套用数位dp模板，但本质是回溯
- P8766 异或三角 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 较为特殊，对二进制位进行异或，并且具有较多的条件
- 三个条件（不妨设b,c<a）：
- a<=n：数位 dp 标准限制 lim
- b,c<n：与lim类似，添加limb、limc
- b^c
#include<bits/stdc++.h>
#define LL long long
#define LF long double
#define pLL pair<LL,LL>
#define pb push_back
//#define fir first
//#define sec second
using namespace std;
//const LL inf;
const LL N=60;
//const LF eps;
//const LL P;
LL T,n,b[N],tot,f[N+5][2][2][2][2];
LL dfs(LL x,LL lim,LL limb,LL limc,LL hav)
{
if(x==0)return hav;
if(f[x][lim][limb][limc][hav]!=-1)return f[x][lim][limb][limc][hav];
LL ans=0;
for(LL i=0;i<=1;i++)//枚举三个变量的取值
for(LL j=0;j<=1;j++)
for(LL k=0;k<=1;k++)
{
//不该出现的lim直接杜绝，该出现的要求用hav记录是否出现，最终决定返回值
if(i+j+k!=0&&i+j+k!=2)continue;//保证异或为零
if(lim&&i>b[x])break;
if(limb&&j>i)break;
if(limc&&k>i)break;
ans+=dfs(x-1,lim&&(i==b[x]),limb&&(j==i),limc&&(k==i),hav||(j+k==2));
}
return f[x][lim][limb][limc][hav]=ans;
}
LL work(LL x)
{
tot=0;
LL ans=0;
while(x)
{
//生成二进制序列
b[++tot]=x%2,x/=2;
}
memset(f,-1,sizeof(f));
return dfs(tot,1,1,1,0)*3ll;//因为假定大小关系，结果还要乘以3
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
printf("%lld\n",work(n));
}
return 0;
}
博弈dp¶
原理¶
对稳赢的理解¶
- 对手回合，无论对手选择什么，最终我都能赢。
- 我的回合，存在一个选项，使得我最终能赢。
模板(记忆化搜索)¶
...dp...//存储结果
bool canWin(string currentState) {
if(...)//特殊情况判断
return...;
return dfs(currentState,1);//记忆化搜索
}
bool dfs(string s,int n)
{
if(...)//访问过，直接返回
return dp[s];
if(...)//游戏结束，判断输赢
{
...
return dp[s];
}
bool a=(n%2==0);//对本回合操作者讨论
for(;;)
{
if(n%2)
{
if(a)//剪枝
break;
a|=dfs(temp,n+1);//本回合是我的回合//有选择我能赢
}
else
{
if(!a)//剪枝
break;
a&=dfs(temp,n+1);//本回合是对手回合//他选什么我都能赢
}
}
dp[s]=a;
return dp[s];
}
例题¶
- 464. 我能赢吗
-
状态压缩+记忆化搜索
- 用dp[i] [j]记录剩余石子状态为i-j时，当前玩家领先的分数
- dp[i][j]=max(piles[i]−dp[i+1][j],piles[j]−dp[i][j−1]),每个玩家都希望自己领先尽可能多的分数
插头dp¶
轮廓线¶
-
将棋盘分割为两个区域，上面是已经完成的区域，下面是还没有开始计算，轮廓线上的区域就是dp正在处理的部分
-
每次枚举轮廓线的下一个点，利用轮廓线的状态进行转移，并移除最旧的点
-
poj2411
-
-
轮廓线的长度与棋盘行一致
-
现在k5将要离开轮廓线，x将要加入，有三种转移方式（0表示点没有被覆盖，1表示覆盖）（现在要决定x上是否摆放、以及摆放的方向）
- 不摆放：要求k5=1;1k4k3k2k1k0->k4k3k2k1k00
- 竖放：要求k5=0
- 横放：k0=0,k5=1
-
- &(~(1<<m))是将移出的部分置零
-
```c++ #include
#include using namespace std; long long dp[2][1<<11]; int now,old; //滚动数组，now指向新的一行，old指向旧的一行 int main(){ int n,m; while( cin>>n>>m && n ){ if(m>n) swap(n,m); //复杂度O(nm*2^m), m较小有利 memset(dp,0,sizeof(dp)); now=0,old=1; //滚动数组 dp[now][(1<<m)-1]=1; //不存在的上一行全置为1
for(int i=0;i<n;i++) //n行 for(int j=0;j<m;j++){ //m列 swap(now,old); //滚动数组，now始终指向最新的一行 memset(dp[now],0,sizeof(dp[now])); for(int k=0;k<(1<<m);k++){ //k：轮廓线上的m格 if(k & 1<<(m-1)) //情况(1)。要求k5=1 dp[now][(k<<1) & (~(1<<m))] += dp[old][k]; //原来的k5=1移到了第m+1位，置0 if(i && !(k & 1<<(m-1) ) ) //情况(2) //i不等于0，即i不是第一行。另外要求k5=0 dp[now][(k<<1)^1] += dp[old][k]; if(j && (!(k&1)) && (k & 1<<(m-1)) ) //情况(3) //j不等于0，即j不是第一列。另外要求k0=0, k5=1 dp[now][((k<<1) | 3) & (~(1<<m))] += dp[old][k];
//k末尾置为11，且原来的k5移到了第m+1位，置0 } }
cout << dp[now][(1<<m)-1]<<endl; } return 0; }```
优化¶
- 优化分类：
- 减少状态总数：剪枝、降维
- 状态转移优化：四边形优化、斜率优化
- 预处理减少递推：hash、单调队列、线段树
滚动数组¶
- 对空间进行优化，即如果dp[i]之和前面固定项而不是多有项相关（如只和dp[i-1]相关）则只需要存储固定数目的相关项，循环利用空间
- 多维dp自我滚动时要注意更新顺序，或者使用交替滚动（一个new一个old）
单调队列优化¶
-
求解滑动窗口内的最值
-
从尾部新加元素维护单调性，并比较头部下标与窗口范围，及时删除过时元素
- 可以用于优化多重背包问题
例题¶
- P3089 Pogo-Cow S
- 由于数据范围中下标范围很大，不适合直接作为dp维度，可以存储从哪个点过来（而不是距离）（按照下标同样具有单调性），就可以大幅优化，类似离散
- P4544 Buying Feed G
斜率优化/凸壳优化¶
平行四边形优化¶
- 通常针对区间dp进行优化，将复杂度降低至\(O(n^2)\)
特殊问题¶
- 动态规划解决约瑟夫问题
- E. Another MEX Problem
- 只使用最短区间用来转移，减少转移次数，实现优化
- P8656 对局匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)