这个专题
着实需要动脑，推转移方程，方程的复杂度，还有优化之处
普通DP
根据题目进行推测
设立状态，然后转移，如：最长不下降子序列
当然，某些题也不会直接是DP板子，而是有些思路
这些DP，之所以归纳为普通，是因为它们都一般是直接for循环有序地DP，不像。。。
背包DP
这个DP归纳出来是因为特殊
背包空间为n，m个物品，每个占空间wi，价值vi，求最大价值
就是那仨板子：
01背包
每个物品只有一个
从后往前转移，因为只能取一个，防止重复
for(int i=1;i<=m;i++){
for(int j=n;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
完全背包
每个物品无穷个
所以随便重复用，不用放置，从前往后
for(int i=1;i<=m;i++){
for(int j=w[i];j<=n;j++){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
多重背包
每个物品限定个数
就是对于一个物品进行ki次01背包
然后有一个优化，就是讲一个ki个的物品拆成几个wi×a+vi×a的物品(a为2^?)，按二进制拆，这样一定有ki个的效果，再跑一遍01背包就行，时间复杂度->log
当然还有单调队列优化
树形背包
就是选了父亲才能选儿子
待补
树形DP
建立在树上，父亲通过儿子转移，巧妙
区间DP
从小区间到大区间的顺序DP，巧妙解决无法转移区间的问题
状压DP
讲一行或一列数压缩进一个数里，有效节省空间和时间
概率DP
对于概率问题的DP，一般设当前状态+解
数位DP
将数拆分成一个个位，然后对于相同的转移部分一次性转移
计数DP
?
插头DP
轮廓线
？
动态DP
？
DP优化
单调队列
就是保留有用的，去掉失去作用的
单调栈
？
斜率优化
推式子
总结
此专题浩若星海，暂不可窥，待修为长进，再做耕耘
标签：21st,背包,18,ki,01,2022,物品,转移,DP From： https://www.cnblogs.com/tlz-place/p/16724070.html