线性dp理解
递推/记忆化搜索，有很多种理解方式
递归重叠子问题的记忆化搜索：
像这里例如 \(f[3]\) 可以通过一次计算得到，保存答案，下一次直接调用即可，省去很多复杂度
我们从此引出dp第一个性质：最优子结构
大问题的最优解包含小问题的最优解，并且小问题的最优解可以推导出大问题的最优解
递推：
我们不管dp[i-1]是多少，但可以从dp[i-1]推导得出dp[i]
dp第二个性质：无后效性
未来与过去无关
dp实现方法
自顶而下：大问题拆解成小问题求解
常用递归+记忆化实现
自底而上：小问题组合成大问题求解
常用制表递推实现
这是最常见的dp方法
背包dp
0/1背包
状态设计
\(dp[i][j]\) 表示只装前i个物品，体积为j时的最大价值
转移方程
\(c[i],v[i]\)表示第i个物品的体积和价值
方式1：
\[dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]) \]方式2：
\[dp[i+1][j+w[i+1]]=max(dp[i+1][j+w[i+1]],dp[i][j]+v[i+1]) \]区别：
方式一是通过上一维来推导这一维，方式二是通过这一维推导下一维
滚动数组
因为看到 \(dp[i][]\) 这一维只与 \(dp[i-1][]\) 这一维有关，所以可以压掉一维，优化空间
交替滚动
用 \(dp[1][]\) 和 \(dp[0][]\) 交替滚动，逻辑清晰，建议初学者食用
int dp[2][N];
int now=0,old=1;
for(int i=1;i<=n;i++){
swap(now,old);
for(int j=0;j<=C;j++){
if(j>=w[i]) dp[now][j]=max(dp[old][j],dp[old][j-w[i]]+c[i]);
else dp[now][j]=dp[old][j];
}
}
自我滚动
int dp[N];
for(int i=1;i<=n;i++){
for(int j=C;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
注:j应该反过来循环，因为 要保证 \(dp[j-w[i]]\) 这一位还是商议维的答案，没有被覆盖掉
规律：只要这一位（i这一位）修改的地方已经用过了，不会再用了，就对答案无影响
分组背包
把物品分为n组，每组只能选一个
只要每组枚举选哪个，0/1背包哪组选或不选就完了
多重背包
规定每种物品有 \(m_i\) 个
暴力解法
把每个物品看成一个独立的物品进行0/1背包
二进制优化多重背包
将 \(m_i\) 按2的倍数从小到大拆，最后是一个小于或等于最大倍数的余数，相当于1个k，2个k，4个k...这些物品进行0/1背包，便可组合出选 \(0~m_i\) 个k的情况，为什么呢，我们看一组例子
在这组例子中，相当于用 \(1k,2k,4k,3k\) 的组合方案来代替 \(0~10k\) 的组合方案，复杂度 \(O(C\sum_{i=1}^n\log_2m_i)\)
单调队列优化多重背包
详见单调队列一章
最长公共子序列
设 \(dp[i][j]\) 表示序列 \(X_{0~i}\) 和序列 \(Y_{0~j}\) 的最长公共子序列长度
当 \(x_i==y_j\) 时：\(dp[i][j]=dp[i-1][j-1]+1\)
当 \(x_i!=y_j\) 时：\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])\)
复杂度 \(O(N^2)\),不是最优解
最长上升子序列
设 \(dp[i]\) 为长度为i的最长上升子序列，最后一个数的大小
对于每一个 \(a[i]\) 找到最大一个 \(dp[j]<a[i]\) 使 \(dp[j+1]=min(dp[j+1],a[i])\)
这个过程可以用二分加速，复杂度 \(O(N\log_2N)\)
P2758 编辑距离
子问题：将 \(X_{1...i}\) 转换成 \(Y_{1...j}\) 的最小操作次数
状态设计： \(dp[i][j]\) 为将 \(X_{1...i}\) 转换成 \(Y_{1...j}\) 的最小操作次数
状转方程：
当 \(X_i==Y_i\) 时：$$dp[i][j]=dp[i-1][j-1]+1$$
当 \(X_i!=Y_i\) 时：$$dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1$$
\(dp[i-1][j-1]\) ：替换 \(X_i\) 为 \(Y_i\)
\(dp[i][j-1]\) ：删除 \(X_i\)
\(dp[i-1][j]\) ：在i位置插入 \(Y_i\)
最小划分
给一个正整数组，把它分为s1,s2两部分，然后求最小的 \(|s1-s2|\)
考虑一部分划分越接近 \(sum/2\) 越优，然后0/1背包做就可以了
ybt题解
背包问题
T2：
考虑首先b中的元素a中一定有，其次b中的元素不能被a中的元素拼成
所以我们先把b数组排个序,然后多重背包转移此数能否被之前书数拼成即可
T3：
多重背包二进制优化板子题
T4：
多重背包，但是状态只有0/1之分
所以我们考虑可以用一种新奇的方式转移
我们用 \(f[i-a[i]]\) 来递推 \(f[i]\) ，若 \(f[i-a[i]]\) 是用了一些 \(a[i]\) 硬币转移过来的，所以它转移到 \(f[i]\) 是又用了一枚硬币才转移过来的，因为硬币个数有限制，所以我们不能无限制的转移下去
存一个 \(cnt[j]\) 表示转移到 \(j\) 共用了多少枚 \(a[i]\) 硬币，判断是否超出范围即可
考虑多重背包为什么不能这样做呢？
猜想：可能是因为多重背包的状态维护的最大价值并不具有转移性质，可能有一个较大的不是用\(a[i]\)来转移的也有可能，反正我不好说
问题暂留，等待各位大佬解答
T5：
注意到每个主件最多有两个附件（首先我没有注意到），并且主件必须先选，考虑选主件的过程相当于是一个0/1背包，而连带的附件又很少
所以将主件和附件依次搭配，作为4种情况，在背包时分讨即可
T6：
板子题，先进行一个0/1背包再进行完全背包即可
T7：
板子题
T8：
比较坑人的一题，首先考虑你的约束条件可以构成几个环，然后我们要求有多少种方案能使得开锁的箱子覆盖所有的环
我们设 \(dp[i][j]\) 表示开j个箱子覆盖i个环的方案数
考虑dp，我们枚举i，然后再枚举j，最后再枚举k表示覆盖i个环开k个箱子，然后转移即可
因为问的是方案，所以要乘一个组合数
注：题目特别坑的地方
考虑组合数，n=300一定爆了，开long long也不行
所以题解中用double存的
唐老师解释说是因为double存的只是一个不精确的数，类似于科学计数法的那种，只存前几位对答案影响大的几位，因为保留4位小数，所以靠后的整数位对答案没有精度影响
T9：
经典dp套路多一个状态就多加一维
设 \(dp[i][v1][v2][0/1]\) 表示选到i数用了v1块1卡，v2块2卡，0/1表示用没用赠送
首先考虑没有必选状态的转移，直接分类讨论，状转式子复杂，代码中有
然后如果有必选状态应该怎么办呢，我们直接截胡，相当于只有选择必选状态的状态才能从这一层i过去，具体实现就是先把所有状态设为-inf，然后能转移的就能更新，否则就不能
题解中的实现是将两种选或不选混在一起写，我选择先把状态必选的刨出来先进行转移用g1存储，不必选的存在g2
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=305,inf=1e9+5;
int v1,v2,n,cnt1,cnt2;
int dp[N][505][55][2];
struct gift{
int p,v;
}g1[N],g2[N];
int main(){
scanf("%d%d%d",&v1,&v2,&n);
for(int i=1;i<=n;i++){
int p,v,s;
scanf("%d%d%d",&p,&v,&s);
if(s) g1[++cnt1]={p,v};
else g2[++cnt2]={p,v};
}
for(int i=1;i<=cnt1;i++){
for(int j1=0;j1<=v1;j1++){
for(int j2=0;j2<=v2;j2++){
dp[i][j1][j2][1]=dp[i][j1][j2][0]=-inf;
dp[i][j1][j2][1]=max(dp[i-1][j1][j2][0]+g1[i].v,dp[i][j1][j2][1]);
if(j1>=g1[i].p){
dp[i][j1][j2][1]=max(dp[i-1][j1-g1[i].p][j2][1]+g1[i].v,dp[i][j1][j2][1]);
dp[i][j1][j2][0]=max(dp[i-1][j1-g1[i].p][j2][0]+g1[i].v,dp[i][j1][j2][0]);
}
if(j2>=g1[i].p){
dp[i][j1][j2][1]=max(dp[i-1][j1][j2-g1[i].p][1]+g1[i].v,dp[i][j1][j2][1]);
dp[i][j1][j2][0]=max(dp[i-1][j1][j2-g1[i].p][0]+g1[i].v,dp[i][j1][j2][0]);
}
}
}
}
// printf("%d\n",dp[cnt1][v1][v2][1]);
for(int i=1;i<=cnt2;i++){
for(int j1=0;j1<=v1;j1++){
for(int j2=0;j2<=v2;j2++){
dp[i+cnt1][j1][j2][0]=dp[i-1+cnt1][j1][j2][0];
dp[i+cnt1][j1][j2][1]=dp[i-1+cnt1][j1][j2][1];
dp[i+cnt1][j1][j2][1]=max(dp[i-1+cnt1][j1][j2][0]+g2[i].v,dp[i+cnt1][j1][j2][1]);
if(j1>=g2[i].p){
dp[i+cnt1][j1][j2][1]=max(dp[i-1+cnt1][j1-g2[i].p][j2][1]+g2[i].v,dp[i+cnt1][j1][j2][1]);
dp[i+cnt1][j1][j2][0]=max(dp[i-1+cnt1][j1-g2[i].p][j2][0]+g2[i].v,dp[i+cnt1][j1][j2][0]);
}
if(j2>=g2[i].p){
dp[i+cnt1][j1][j2][1]=max(dp[i-1+cnt1][j1][j2-g2[i].p][1]+g2[i].v,dp[i+cnt1][j1][j2][1]);
dp[i+cnt1][j1][j2][0]=max(dp[i-1+cnt1][j1][j2-g2[i].p][0]+g2[i].v,dp[i+cnt1][j1][j2][0]);
}
}
}
}
if(dp[n][v1][v2][1]<0) printf("-1");
else printf("%d",dp[n][v1][v2][1]);
}