DP是真的难啊，感觉始终不入门路，还是太弱了┭┮﹏┭┮
DAG上的DP
一般而言，题目中如果存在明显的严格偏序关系，并且求依靠此关系的最大/最小值，那么考虑是求DAG上的最短路或者是最长路。(据说还有路径计数的问题，我倒是没遇到，哪位大大看见提醒一下呐)
这类问题可以使用记忆化搜索直接解，但是有爆栈的风险。
数据比较大的情况下，可以使用先求拓扑序，然后按照拓扑序（bfs求拓扑序），进行递推即可。
背包问题
1.完全背包
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; ++j)
f[j] = max(f[j],f[j - w[i]] + v[i]);
完全背包本质就是一个DAG问题，把背包的剩余容量看成状态，边就是物品的体积。
2.01背包
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
if (j < w[i])
f[i][j] = f[i-1][j];
else
f[i][j] = max(f[i-1][j],f[i-1][j-w[i]] + v[i]);
简化后
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; ++j)
f[j] = max(f[j],f[j - w[i]] + v[i]);
01背包按刘汝佳的话说是一个多阶段决策问题，或者说是二维dp，也即是需要一个维度来考虑对于物品的使用。
3.多重背包
int f[N],v[N],w[N],n;
for (int i = 1; i <= n0; i++)
{
cin >> wi >> vi >> ci;
for (int j = 1; j <= ci; j <<= 1;)
{
++n;
v[n] = vi * j;
w[n] = wi * j;
ci -= j;
}
if (c > 0)
{
++n;
v[n] = vi * c;
w[n] = wi * c;
}
}
for (int i = 1 ; i <= n; i++)
for (int j = m ; j >= w[i]; j--)
{
f[j] = max(f[j],f[j-w[i]] + v[i]);
}
把未知模型拆分为已知的模型， 把多重背包拆分成多个01背包，具体原则就是把一个数用logn(n为重复个数)来进行表示，使得物品的数量变成O(nlogm),然后复杂度变为O(nmlogm)
4.分组背包
for (int i = 1 ; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= len[i]; k++)
{
if(j - g[i][k])
f[j] = max(f[j],f[j-w[i][k]]+v[i][k]);
}
在01背包的基础上,每个物品属于一个组，每组中的物品是互斥的。
5.树形背包
在01背包的基础上，每个物品可能依赖于某个其他物品(需要选定某个前驱物品，才能选这个物品）
1.得到dfs序，和每个结点对应的最远子树结点r
2.按照dfs序从后往前，对于每件物品，考虑它选/不选两种情况如果不选，对应的整颗子树也不选，变成dfs序中子树最后一个的下一个 如果选，变成dfs序中的下一个。
LIS问题
dp[i]表示序列1~i的LCS，进行dp转移即可。
for (int i = 1; i <= n ; i++)
for (int j = 1; j < i; j++)
if (j < i) dp[i] = max(dp[i],dp[j]+1)
可以用树状数组优化,最终结果为dp[n]
LCS问题
dp[i][j]表示第一个序列1j位置的LCS。
for(int i = 1; i <= n1; i++)
for(int j = 1;j<=n2;j++)
if (i==j)dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i-1][J],dp[i][j-1]);
最终结果为dp[n1][n2];