# 动态规划（DP）
## 背包
**基本套路**：
- 对所有候选物品依次观察，要么不取，要么符合条件地取
- 在只用当前观察物品和之前观察过的物品的情况下，不断更新某容量时的最优解
- 直到观察完最后一个物品，就得到了最终需要的容量及其最优解
**例1**：01背包
$dp[i][j]=\begin{cases}dp[i-1][j],&j < w_i\\ \max(dp[i-1][j-w_i] + val_i, dp[i-1][j]), &j \ge w_i\end{cases}$
**例2**：完全背包
$dp[i][j]=\begin{cases}dp[i-1][j],&j < w_i\\ \max(dp[i][j-w_i] + val_i, dp[i-1][j]), &j \ge w_i\end{cases}$
求情况数：[背包问题求情况数](/blog/note/4813f54385e64dd5942c77c0ebd14185)
**例3**：硬币组合：给出无限多面值为1、5、10、25、50的硬币
- 需要的最少硬币数：$dp[i][j]=\begin{cases}dp[i-1][j],&j<v_i\\ dp[i][j-v_i]+1,&j\ge v_i\end{cases}$
- 最少硬币的具体组合：
- 在上式选择第二分支时，记录`last_coin[j]`=$v_i$。最终逆推`last_coin`，即有一个最少硬币组合
- 所有可行组合个数：$dp[i][j]=\begin{cases}dp[i-1][j],&j<v_i\\ dp[i-1][j]+dp[i][j-v_i],&j\ge v_i\end{cases}$
- 所有可行组合个数（限制硬币总共最多100枚）：$dp[i][j][k]=\begin{cases}1,&i, j,k=0\\ dp[i-1][j][k],&i>0\land j<v_i\\ dp[i-1][j][k]+dp[i-1][j-v_i][k-1],&i>0\land j\ge v_i \land k>0\\ 0,&others\end{cases}$
- $i$：观察的硬币，$j$：总面值，$k$：硬币个数
## LCS/LIS
**LCS**：
$$
LCS[i][j]=\begin{cases}
LCS[i-1][j-1] + 1, &a[i]=b[j], \\
\max(LCS[i-1][j], LCS[i][j-1]), &a[i]\ne b[j].
\end{cases}
$$
**最小回文距离**：求把a变成回文串需要增删的字符数，直接求a和a反转的LCS，算与a长度的差值即可
**最小编辑距离**：求把a变成b需要增删改的字符数
$$
dp[i][j]=\begin{cases}
i,&j=0\\
j,&i=0\\
dp[i-1][j-1],&a[i]=b[j]\\
1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]),&a[i]\ne b[j]
\end{cases}
$$
**LIS**：
$$
\max_i LIS[i]=1 + \max_j (0,LIS[j]),\; 0<j<i\ \land\ a[j]<a[i]\\
$$
## 状压
**基本套路**：
- $dp[state][...]$，$state$ 是将一些布尔代数实体压缩为数字的结果，典型的比如0-1状态、集合元素等，也可以通过进制转换扩展到多状态（如三状态、四状态）
- 操作：
- 遍历每种状态：直接for循环即可
- 判断第`i`位（从0开始）是否为1：`a & (1<<i)`
- 第`i`位设置为1：`a |= 1<<i`
- 第`i`位设置为0：`a &= ~(1<<i)`
- 清除最低为1位：`a &= a-1`
- 只保留最低为1位：`a &= -a`，即树状数组的`#define lowbit(x) (x&(-x))`
## 区间
**基本套路**：
- 从长度为1的区间开始，递推长度为2的区间……直到推满长度
- 倍增ST表���构建是一个区间递推，但不是逐长度，而是逐2的幂次长度
**例1**：石子合并。有n堆石子排成一排，两两之间可合并，代价为两堆重量之和，求将所有堆合并的最少代价
$$
dp[i][j]=\begin{cases}
0, &j=i \\
w_i+w_j, &j=i+1 \\
\displaystyle\sum_{x=i}^j w_x + \min_k(dp[i][k]+dp[k+1][j]), &j>i+1, i\le k<j
\end{cases}
$$
其中求和用前缀和预先求
## 树形 / DAG
**基本套路：**
- $dp[n][i]$，$n$为当前节点，$i$为节点可取的状态。状态转移从树或DAG结构出发
- 在树上，有时对后代和祖先的状态转移是不同的，对根节点也可能不同，需分类讨论
## 数位
**基本套路：**
- $dp[i][j] = \sum_{y=0}^9 f(dp[i-1][y], digit[j])$，代表最高位为 $j$ 的 $i$ 位数下符合给定条件的状态值。其为最高位为 $y$ 的 $i-1$ 位数在前位数字 $j$ 条件下的状态值的聚合。
- 求出后按照给定的数字区间进行聚合，`agg(L,R)=agg(0,R)-agg(0,L-1)`
- 注意：
- ①初始化值要仔细推
- ②最后聚合时最高位打头下放计算，最高位已经不满足条件的不下放！
- ③最后聚合时注意0值和前导0是否需要计算
**例1**：不超过3个非0数位的数字个数：
$dp[i][j][k] = \sum_{y=0}^9 dp[i-1][y][digit[j]?k-1:k]$
**例2**：不含4的数字个数：
$dp[i][j] = \sum_{y=0}^9 dp[i-1][y],\;j\ne4\ \land\ y\ne4$
处理 $y\ne4$ 是在 DP 构造阶段，处理 $j\ne4$ 既要在DP构造阶段，也要在聚合阶段，特别注意
**例3**：HDU 6148
## x概率
![]()