背包问题0-1背包dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]d[i]);for(int i1;in;i) for(int jm;jw[i];j--) dp[j]max(dp[j],dp[j-w[i]]d[i]);n数量m容量w[i]代价,d[i]价值完全背包for(int i1;in;i) for(int jw[i];jm;j) dp[j]max(dp[j],dp[j-w[i]]d[i]);n数量m容量w[i]代价,d[i]价值多重背包问题将每一样物品有kkk个转化成有kkk个相同的物品每个只能选择111次即可快速转化为0−10-10−1背包类似问题快速解决题目。普通版本dp[0][0]1; for(int i1;in;i) for(int jm;j0;j--) for(int k0;kmin(j,cnt[i]);k) dp[i][j](dp[i][j]dp[i-1][j-k])%mod;滚动数组优化版本dp[0]1; for(int i1;in;i) for(int jm;j0;j--)//一定要倒序防止污染正确数据 for(int int k1;kmin(j,cnt[i]);k) dp[j](dp[j]dp[j-k])%mod;二进制拆分优化版本针对输入进行优化log级别O(nWm)−O(nWlogm)O(nWm)-O(nW logm)O(nWm)−O(nWlogm)原理是基于二进制拆分可以实现所有数字的组合for(int i1;in;i) { cinvwm;//m表示个数 for(int k1;km;k*2) { items.push_back({v*k,w*k}); m-k; } if(m0) items.push_back({v*m,w*m}); }items中存储了处理完的wiw_iwi​和viv_ivi​注意初始化和循环正负序。基础线性DP状压DP状压DP基本操作x k将二进制下xxx每一位左移一个位置x k将二进制下xxx每一位右移一个位置s(1k)判断二进制下第kkk位是不是111s s | (1k)将sss第kkk位赋值为111s (s1)判断sss相邻位置有没有111棋盘状压DP基本套路dp[i][j][A]表示前i行用j个XX,当前行的状态为A时候的最佳答案dp[i][A][B]表示前i行当前行状态为A,前一行状态为B时候的最佳答案转移通常为直接检查是否可以转移然后直接进行暴力转移 dp[i][j][A]max(dp[i][j][A],dp[i-1][j-1][B])典型题目P1896 P1979TSP 状压DP基本套路dp[S][i]表示当前去状态为S当前位置为i时的最佳答案枚举顺序为当前各点状态当前位置下一位置。另外应当判断所在点是否与最外重循环匹配不匹配可直接跳过。P1433核心代码for(int S0;S(1n);S) { for(int i0;in;i)//当前所在位置 { if(!(S(1i))) continue; for(int j0;jn;j)//将要转移到的位置 { if(S(1j)) continue; dp[S | (1j)][j]min(dp[S][i]dist(a[i],a[j]),dp[S | (1j)][j]); } } }树形DP关键区别从线性上的递推变成了在树上进行递推并且是从叶子节点向上向根节点进行递推。选择节点类dp[i][0]dp[j][1] dp[i][1]max(dp[j][1],dp[j][0])树上背包dp[v][k]dp[u][k]val dp[u][k]max(dp[u][k],dp[v][k-1])例题P2014选课for(auto v:G[u]) { dfs(v); for(int jm1;j1;j--) for(int k1;kj;k) dp[u][j]max(dp[u][j],dp[u][j-k]dp[v][k]); }换根DP树形 DP 中的换根 DP 问题又被称为二次扫描通常不会指定根结点并且根结点的变化会对一些值例如子结点深度和、点权和等产生影响主要特征会问你最佳点是哪里状态通常定义为dp[i]表示以i为根的答案一般策略为先dfs处理一次一般处理子树大小等不会因根不同而改变的因素再dfs一次进行dp求答案P3478代码s[i]表示以i为节点的子树大小 void dfs(int u,int fa,int dep) { for(auto to:G[u]) { if(tofa) continue; dfs(to,u,dep1); s[u]s[to]; } s[u]1; dp[1]dep; } void dfsdp(int u,int fa) { for(auto to:G[u]) { if(tofa) continue; dp[to]dp[u](n-s[to])-(s[to]); dfsdp(to,u); } }