线性dp：

• LIS：

严格上升：*lower_bound(f+1,f+1+n,a[i]) = a[i];

非严格上升：*upper_bound(f+1,f+1+n,a[i]) = a[i];

• LCS: 最长公共子序列

背包dp:

• 01背包：每种物品只能取一件

• 完全背包：每种物品可以取无数件

• 多重背包：每种物品有固定件数。

可进行二进制拆分优化。

• 分组背包：对不同组做背包就可以了。

区间dp:

• 枚举区间长度

• 枚举区间起点

• 枚举区间断点

树形dp:

• $f[i][j]$ 中的 i 用来表示结点， j 用来表示状态信息。

状压dp：

数位dp：

记忆化搜索

类似dp。先写出dp方程然后在搜索中利用记忆化数组记录最优解。（剪枝？）