背包 $\mathbf{DP}$
$DP$ 的背包问题是最基础的 $DP$ 了，分为 $01$ 背包，完全背包和多重背包。
$\mathbf{01}$ 背包
$01$ 背包基本模型，背包的总体积为 $V$ ，总共有 $n$
件物体，每件物品的体积为 $v_i$ ，价值为 $w_i$
，每件物品只有一个，选择一个集合 $\mathbb{S}$ ，在满足
$\sum_{i\in \mathbb{S}} v_i\leq V$ 的前提下最大化
$\sum_{i\in \mathbb{S}} w_i$
。可以很快推得状态转移方程为：$dp[i]=\max(dp[i],dp[i-v[j]]+w[j])$
时间复杂度为 $\Theta(n^2)$ 。
完全背包
完全背包基本模型，背包的总体积为 $V$ ，总共有 $n$
件物体，每件物品的体积为 $v_i$，价值为 $w_i$
，每个物品有无限多个，选择一个集合 $\mathbb{S}$ ，在满足
$\sum_{i\in \mathbb{S}} v_i\leq V$ 的前提下最大化
$\sum_{i\in \mathbb{S}} w_i$ 。其实就是在 $01$
背包的基础上做了一点修改。 $01$
背包每件物品都只有一个，所有我们枚举物品时需要倒序枚举防止重复。完全背包允许重复，我们应该正序枚举。状态转移方程仍为：$dp[i]=\max(dp[i],dp[i-v[j]]+w[j])$
时间复杂度为 $\Theta(n^2)$ 。
多重背包
多重背包基本模型，背包的总体积为 $V$ ，总共有 $n$
件物体，每件物品的体积为 $v_i$ ，价值为 $w_i$ ，每个物品有 $n_i$
个，选择一个集合 $\mathbb{S}$ ，在满足
$\sum_{i\in \mathbb{S}} v_i\leq V$ 的前提下最大化
$\sum_{i\in \mathbb{S}} w_i$ 。考虑分解为 $01$ 背包，将每个物体拆分成
$n_i$ 个，再进行 $DP$ 。这样的时间复杂度为
$\Theta((\sum_{i=1}^n n_i)^2)$
。考虑优化。我们可以尽量少的进行拆分，使用二进制拆分将一种物品拆分为
$2^k (k=0,1,2 \cdots)$
个为一个新物品，这样可以满足取任意个，不影响答案。时间复杂度降低为
$\Theta((\sum_{i=1}^n \log_2 n_i)^2)$
分组背包
一般分组背包问题中，每组中只能选择一件物品。设 $dp[i][j]$ 代表前 $i$
组物品构成体积为 $j$ 的背包所能取得的最大价值和。状态转移方程易得
$dp[i][j]=\max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])$
树形 $\mathbf{DP}$
树形 $DP$ 的一般形式都是对子树的信息进行归并，其本质是 $dfs/bfs$
过程中的统计。有些时候，还会涉及组合等方面的知识。时间复杂度一般为
$\Theta(n)$ 。
区间 $\mathbf{DP}$
区间 $DP$ 的本质就是对区间信息的合并。在区间 $DP$
中，我们可以通过对区间信息的合并，解决一系列问题。
数位 $\mathbf{DP}$
数位 $DP$ 的一般形式是求出在给定区间 $[L,R]$ 内，符合条件 $f(i)$ 的数
$i$ 的个数。条件 $f(i)$
一般与数的大小无关，而与数的组成有关。一般使用记忆化搜索实现数位 $DP$
。从起点向下搜索，到最底层得到方案数，一层一层向上返回答案并累加，最后从搜索起点得到最终答案。一般来说，数位
$DP$ 解决区间 $[L,R]$ 的时候，会将其变成 $[0/1,R]-[0/1,L-1]$ 。
状态压缩 $\mathbf{DP}$
一般来说，使用状压 $DP$
是因为状态转移不得不使用到更加细节的信息，但如果细节信息单独储存又没有足够的空间，于是考虑用一个数表示一个状态，用这个数的二进制来储存细节信息。状压
$DP$ 需要大量的位运算技巧，现列举一些常用技巧：
- 取出数字 $x$ 第 $i$ 位： $((x>>(i-1))\&1$ 。
- 将数字 $x$ 第 $i$ 位取反： $x^{\land}=(1<<(i-1))$ 。
- 将数字 $x$ 第 $i$ 位置 $1$ ： $x|=(1<<(i-1))$ 。
- 将数字 $x$ 第 $i$ 位置 $0$ ： $x\&=(1<<(i-1))$ 。
- 将数字 $x$ 最靠右的 $1$ 去掉： $x=x\&(x-1)$ 。
- 取出数字 $x$ 最靠右的 $1$ ： $x\&(-x)$ 。
- 判断数字 $x$ 是否有两个连续的 $1$ ： $if(x\&(x<<1))$ 。\
一般来说，状压 $DP$ 数据范围在 $20$ 左右，可以用一个 $int$ 储存状态。
概率&期望 $\mathbf{DP}$
概率
概率亦称”或然率”。它反映随机事件出现的可能性大小。首先列举一些公式:
$P(\mathbb{S}-A)=1-P(A)$ $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ 定义如果
$A$ 发生，那么 $B$ 发生的概率为 $P(B|A)$ ，可以得到
$P(B|A)=\frac{P(A\cap B)}{P(A)}$ 假如有 $n$ 个事件 $B_1,B_2,B_3\cdots$
，且有 $\forall i,\forall j,B_i\cap B_j=\varnothing$
，$\bigcup_{i=1}^n B_i=\mathbb{S}$ ，那么有全概率公式
$P(A)=\sum_{i=1}^n P(B_i)\cdot P(A|B_i)$ 还有一个贝利叶公式
$P(B|A)=\frac{P(B)\cdot P(A|B)}{P(A)}$ 求概率是可以根据需要使用。
期望
数学期望，简称期望，是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。期望的基本算法为
$E(x)=\sum_{i=1}^{\infty} x_i\cdot p_i$ 。期望具有可加性，即
$E(x+y)=E(x)+E(y)$ ，也有 $E(a\cdot x)=a\cdot E(x)$ 。在 $DP$ 时经常使用这一性质。
$\mathbf{DP}$ 优化
单调队列优化
单调队列是一种数据结构，通过双端队列实现在 $\Theta(1)$
的时间复杂度内获得区间最值。在许多转移方程带 $\max \min$ 的 $DP$
中，它可以很好地优化。
斜率优化
有一类问题，将n个物品分为连续的若干份，每分一次会通过一个计算方式产生一个代价，问代价最大/最小是多少。考虑
$DP$ ，容易想到状态转移方程为
$dp[i]=\min(\max)\left\{dp[j]+val(i,j)\right\}$ 算法复杂度为
$\Theta(n^2)$
当代价为该段物品的价格之和时，可以用单调队列优化解决。但是当代价为该段物品的价格之和的平方，即
$dp[i]=\min(\max)\left\{dp[j]+(sum[i]-sum[j])^2\right\}$
此时单调队列不可维护，此时考虑斜率优化。设 $\exists k(j>k)$
使得转移更优。那么可得
$dp[j]+(sum[i]-sum[j])^2<dp[k]+(sum[i]-sum[k])^2$ 展开整理，得
$dp[j]-dp[k]+sum[j]^2-sum[k]^2<2\cdot sum[i]\cdot (sum[j]-sum[k])$
再次整理，将其化为分式
$\frac{dp[j]-dp[k]+sum[j]^2-sum[k]^2}{sum[j]-sum[k]}<2\cdot sum[i]$ 令
$f(x)=dp[x]+sum[x]^2$ 可得 $\frac{f(j)-f(k)}{sum[j]-sum[k]}<2\cdot sum[i]$
观察这个式子，发现其很像斜率，在空间中绘出点 $(sum[x],f(x))$
，可以发现转移的最优的点始终在一个下凸壳上，用数据结构维护即可。