瞎dp
最大子序列
dp方程：
f=max(f,f+a);
ans=max{f};
背包问题
0/1背包问题：
f(i,j)表示前i个物品装j时候的最大价值
考虑每个物品选与不选
不选：f(i,j)=f(i-1,j);
选：f(i,j)=f(i-1,j-v[i])+cost[i];
降维：
i:1 to n;j:maxv to v[i]
多重背包问题：
由0/1背包演变而来
f(i,j)表示前i个物品装j时候的最大价值
其中k(0<=k<=num[i])表示当前选了k个第i件物品
则状态转移方程为：
f(i,j)=max{f(i-1,j-v[i]*k)+c[i]*k};
降维：
i:1 to n;j:maxv to v[i];k:num[i] to 1
注意j-v[i]*k>=0
完全背包问题：
由多重背包演变而来
将num[i]默认为j/v[i]即可
降维：
与前两个背包不同的是，完全背包可降时间和空间，方法是只用i j两个变量顺推：
i:1 to n;j:v[i] to maxv
分组背包问题：
对每一组的背包进行0/1背包
定义数组a[][]:
a[k][0]:第k组的物品数量;a[k][i]:第k组第i件物品的数量
定义t:记录整个组数
与0/1背包不同的是：先枚举体积再枚举个数且个数顺推
即枚举顺序为：
组数k:1 to t;体积j:maxv to 0(0是因为不知道当前的v[i]);个数i:1 to a[k][0]
注意j大于v[a[k][i]]
最长上升子序列LIS
nlogn解法：
令cnt为答案。
mark[k]：长度为k的上升子序列的最末元素。
若有多个，则记录最小的那一个(贪心)
利用mark的单调性进行二分查找t,
t为当前元素插入进去后的位置(即当前长度。
如果t大于cnt,cnt++
最长公共子序列
nlogn解法还不怎么清楚，n^2解法：
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
最长抖动序列
令f[],g[]分别为上升，下降的最大长度(针对于最后一个元素)。
对于h[i]：考虑h[i]的选与不选
讨论：
case 1:h[i]==h[i-1]:f[i]=f[i-1];g[i]=g[i-1];
case 2:h[i]>h[i-1]:f[i]=max(g[i-1]+1,f[i-1]);f[i]=f[i-1];
case 3:h[i]<h[i-1]:g[i]=max(f[i-1]+1,g[i-1]);g[i]=g[i-1];
序列分组
序列分组：
把n个元素分成k组，分两步：
1、把前i个元素分成k-1组
2、把剩下的元素分成第k组
则f(dn,dk)=f(i,dk-1) op g[i+1][dn];
ans=(n,k);
边界：
f(dn,1),前dn个元素分成一组。
循环式：
1、枚举分组dk(2 to k) //dk=1是边界 dk从2开始枚举
2、枚举终点dn(dk to n) //要分成dk组 至少是dk个元素
3、枚举前di个元素分成dk-1组，剩余di+1到n分成第dk组：d(dk-1 to (dn))