疑似题单和笔记的结合体……写的十分简略但尽量做到周全要点，求点赞，求推广/kel

---

区间dp

• 一般在一段序列上进行
• 当前区间的答案可以通过枚举断点的形式由两段相邻的子区间的答案合并而来
• 时间复杂度多为 $O(n^{3})$（枚举区间长度1层，枚举左端点1层，枚举断点1层，共3层循环）
• 状态设计多为 $f[L][R]$表示区间 $[L,R]$的答案
• 事实上，大多数区间dp题的难点在于看出它是区间dp和不重不漏地合并区间得到新区间的答案

例题：POJ2955，POJ1651，HDU4632（洛谷上的我就不摘了，反正题单上有的是qwq）

背包

$n$个物品，体积为 $m$的包，每个物品有价值v和体积w，在总体积小于等于 $m$的条件下最大化物品价值的和。

状态设计：一般用 $f[i][j]$表示前 $i$个物品已考虑完毕，恰好占 $j$的体积所能达到的最大价值

01背包

• 每个物品只能选一次
• $f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})$
• 可以通过倒序枚举来压维

完全背包（又称无穷背包）

• 每个物品可以选无穷次
• $f_{i,j}=\max(f_{i-1,j},f_{i,j-w_{i}}+v_{i})$
• 可以通过正序枚举来压维

多重背包

• 每个物品可以选有限的 $k$次
• 把一个物品拆成 $k$个相同的物品转化为01背包
• 发现可以通过二进制拆分来优化上述过程

混合背包

• 将完全背包和多重背包混合在一起
• “见人下菜碟”，它是什么种类就用什么转移方程（实质上是遍历顺序的不同）

分组背包

• 咕咕咕

例题：P1833，P4095

树形dp

• 树上的dp
• 时间复杂度常为 $O(n)$
• 通过自上向下dfs进行转移
• 关键点在于恰当地合并儿子结点的答案

例题：HDU2376，SP1437

数位dp

• 一位一位地做dp
• 状态通常为dp[i][0/1]表示从高到低填到第i位，前i位与x相比是小于/等于时的答案
• 经常需要处理前导零以及把区间[L,R]转换为两次前缀
• 时间复杂度通常与位数有关。

排列dp

• 非常罕见的dp，dp的对象是1~n的排列
• 用dp[i]表示1~i的排列
• 转移一般都是从小到大/从大到小

状压dp

• 以一个二进制数作为状态设计，这个二进制数每一位的0/1都对应着一个状态。
• 时空复杂度通常为 $O(2^{n})/O(4^{n})$再乘以一个数
• 因此，n的数据范围一般是10~12/20~24
• 有很多优化时间复杂度的方法，比如说预处理出合法的状态、枚举子集等。
• 枚举子集：for(int i=x;i;i=(i-1)&x)

博弈论dp

• 只研究二人博弈
• 分两种：简单的二人博弈和组合博弈
• 简单的二人博弈：记忆化搜索，f[i]表示场景i是必胜态还是必败态
• 组合博弈：sg函数和sg值，sg[i]表示场景i的sg值是多少（0-必败 1-必胜）， $sg[i]=mex(S)$，其中S为状态i向后所能到达的所有状态的sg值的集合。求n个游戏的组合的结果就需要用到sg定理： $sg(a1,a2,a3,…,an)$= $sg(a1) \oplus sg(a2) \oplus sg(a3) \oplus…\oplus sg(an)$
• nim石子游戏其实就是组合博弈问题中sg(i)=i的特殊情况

  期望dp

• 蒟蒻还没学会:(

（特殊类型的dp已完毕，接下来是优化类的dp）

矩乘优化dp

• 两种形式：

• 加速数列递推(P3216)或
• 处理形如 $dp[i][j]=\sum_{k=1}^{n}dp[i-1][k]\times Z[k][j]$的转移方程（也就是第i行始终由第i-1行的每个元素乘上对应的转移系数再求和转移的形式，其中转移系数不能与 $i$有关）（P4159）