DP可以算是最灵活多变的一种题型，没有固定的算法或者公式，重点在于熟悉每个类型的基本模板。
背包问题是我们最早接触的DP类型，类型有很多，今年的真题D1T2就可以看成一个完全背包。
在这类问题里面，对于每种物品有ci和wi两个值，并且只有选择和不选择两种状态，需要求出在有限的Σc中使Σw最大
这样的问题，标准思路是开一个二维数组，但是由于每个数据只和上一行有关，可以使用滚动数组，但是更好的办法是降维。
如何降维？
我们假设f[i]表示刚好装满i空间时的最大价值，j为当前状态，那么关于任何一个物品，f[i + ci] = max(f[i + cj], f[i] + wj)
注意：每一次装包时要从后往前，不然相同物品会被重复放入，最后输出答案不能直接输出f[m]，而是输出f[1]到f[m]的最大值
完全背包：每个物品选取任意次，传送门，正向遍历即可
组合背包：有些物品选取时必须选取另一种物品，基础方程的max中考虑这些情况即可 传送门
部分背包：每个物品可以选取非整数个，c与w成比例，这个最简单，直接求性价比然后贪心就o98k了
多维背包：背包容量有多个参数，这玩意还是记忆化搜索比较靠谱，传送门 传送门
典型模板：最长上升子序列
这个就比较简单了，对于每个状态f[i]，在f[1]到f[i - 1]中选取最大值加一即可
这种问题一般分为两种，我暂且将它成为邻居问题和裁剪问题
大意：当一个节点被标记后，它的邻居节点就会被覆盖，求覆盖整个树的最少标记
这种问题说白了只能记忆化搜索，因为你遍历一棵树也是基于DFS的操作
对树进行裁剪，只能删除，不能改变以前的结构，在留下的边权在m之内，使剩余点权最大
这种问题可以当做背包来考虑，但是要从椰子往跟判断
这种问题大体思路就是枚举区间长度，然后在区间内按照题意模拟即可
例题：P1880
这种问题一般是在一个二维矩阵上，修改一个点一般会对上下左右的点产生影响，一般我们使用一个二进制数存一行的状态（每一位01表示是否覆盖），然后与上一行与，左右位运算再与上一行与，看是否为零来判断有没有互相影响，这样就能把状态压缩到一行。
这种问题一般是区间最值，一般使用一个队列，把小于后点的前点删掉，过期点删掉，每次就可以只考虑队尾
斜率优化：对于一些特殊的DP，它的状态转移方程可以转换成一次函数的形式，然后用单调队列处理它每个状态的斜率（图像上凸的点删掉），就可以省略掉很多状态，然后移动截距即可
例题：P2365
第一眼看到动规的题，如果想不出思路，一定要用Dfs打一个暴力，但是在打完暴力之后，也许修改一下Dfs，就可以成为复杂度正确的记忆化搜索
这是一个典型的Dfs暴力程序：
int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
if( tleft < 0 ) return;
if( pos == n+1 ){
ans = max(ans,tans);
return;
}
dfs(pos+1,tleft,tans);
dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
cin >> t >> n;
for(int i = 1;i <= n;i++)
cin >> tcost[i] >> mget[i];
dfs(1,t,0);
cout << ans << endl;
return 0;
}
然后开一个二维数组，修改一下Dfs函数，就成为了记忆化
int n,t;
int tcost[103],mget[103];
int mem[103][1003];
int dfs(int pos,int tleft){
if( mem[pos][tleft] != -1 ) return mem[pos][tleft];
if(pos == n+1)
return mem[pos][tleft] = 0;
int dfs1,dfs2 = -INF;
dfs1 = dfs(pos+1,tleft);
if( tleft >= tcost[pos] )
dfs2 = dfs(pos+1,tleft-tcost[pos]) + mget[pos];
return mem[pos][tleft] = max(dfs1,dfs2);
}
int main(){
memset(mem,-1,sizeof(mem));
cin >> t >> n;
for(int i = 1;i <= n;i++)
cin >> tcost[i] >> mget[i];
cout << dfs(1,t) << endl;
return 0;
}
看了LSY神犇的介绍，我发现脑洞大开，于是把今年的真题D1T2用记忆化搜索敲出来了
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXM = 25000, MAXN = 100;
bool v[MAXM + 1];
int t, n, a[MAXN + 1];
bool Dfs(int val, int pos)//当前价值，当前货币种类
{
if(val + pos >= MAXM)//边界
return 0;
if(v[pos + val])//如果这种价值能被之前的货币表示出来
{
int nxt = 0;
for(int i = pos + 1; i <= MAXM; i++)
if(v[i]){
nxt = i;
break;
}//找到下一个能表示出来的价值
if(nxt)
return Dfs(val, nxt);//这种货币需不需要就取决于下一种用不用它
else return 0;
}
else//如果不能被表示出来
{
v[pos + val] = 1;
int nxt = 0;
for(int i = pos + 1; i <= MAXM; i++)
if(v[i]){
nxt = i;
break;
}
if(nxt)
Dfs(val, nxt);
return 1;//这种货币肯定需要，但是接下来的价值还是需要处理
}
}
int main()
{
cin >> t;
while(t--)
{
cin >> n;
memset(a, 0, sizeof(a));
memset(v, 0, sizeof(v));
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
int ans = n;
for(int i = 1; i <= n; i++)
if(!Dfs(a[i], 0)) ans--;
cout << ans << endl;
}
return 0;
}
优点：好想
缺点：没法使用滚动数组，要是内存占用大的话只能考虑降低维度
原文：https://www.cnblogs.com/Juruo1103/p/10098122.html