$\max$ 也符合。

注意：本文只是最基础的一些方程形式（并不是完全的），如果遇到斜率优化等算法不要方程多加了点状态就区分不出来了！

1. 线性递推方程（Linear Recurrence Relations）

线性递推方程 是最常见的动态规划方程，形式如下：

$ dp[i] = \min_{j < i} (dp[j] + f(j, i)) $

其中，$f(j, i)$ 是状态转移的代价函数。

优化技术：

• 斜率优化：用于优化类似于以下形式的线性递推关系：

$ dp[i] = \min_{j < i} (dp[j] + a_j \cdot b_i) $

其中 $a_j$ 和 $b_i$ 是线性函数。通过维护一个凸包来快速找到最优值。

• 单调队列优化：用于处理滑动窗口或单调性问题，通过单调队列来减少状态转移的复杂度。

• 线段树优化：用于处理具有区间查询的线性递推方程，通过线段树来快速处理区间最优值查询。

• 二分栈优化：二分栈优化包括了$w_{i,j}$，所以需要借助四边形不等式判断决策单调性。

• 分治：二分栈有一个局限性，那就是必须能快速计算$w_{i,j}$。可以离线用分治计算。

• WQS二分/带权二分/凸包优化 符合单调性可用

• 矩阵优化：广义矩阵，要求决策点少

2. 区间DP方程（Interval DP）

区间DP方程 处理的是区间划分或区间合并的问题，形式如下：

$ dp[i][j] = \min_{k \in [i, j]} (dp[i][k] + dp[k+1][j] + cost(i, j)) $

其中，$cost(i, j)$ 是划分区间 $[i, j]$ 的代价。

优化技术：

• 四边形不等式优化：当代价函数 $cost(i, j)$ 满足四边形不等式时，可以通过利用四边形不等式减少状态转移的计算量。四边形不等式的形式为：

$a \leq b \leq c \leq d $
$ cost(a, c) + cost(b, d) \leq cost(a, d) + cost(b, c) $

决策单调型优化：在某些情况下，状态转移的决策具有单调性，可以通过减少枚举范围来优化计算。

3. 状态压缩DP方程（State Compression DP）

状态压缩DP方程 处理的是状态空间较大的问题，形式为：

$ dp[mask] = \min_{submask \text{ is a valid subset}} (dp[submask] + cost(submask, mask)) $

其中，$mask$ 是状态的位掩码表示。

优化技术：

• 位运算优化：通过位运算高效地处理状态压缩问题，如计算子集代价。

• 滚动数组优化：对于某些状态压缩问题，可以使用滚动数组减少空间复杂度。

• 子集卷积优化：针对$O(3^n)$算法的优化。

4. 多阶段决策DP方程

处理的是多个阶段决策的问题，形式为：

$ dp[i][j] = \min_{k \text{ in stages}} (dp[i-1][k] + cost(k, j)) $
$ dp[i][j] = \min_{x \text{ in sub of i}} (dp[x][y] + …) $

优化技术：

• 矩阵优化：广义矩阵，要求决策点少，还可以解决有向图中求合法路径方案数

• 换根：对于树形结构的决策问题，利用树的结构特性来优化状态转移。

此外还有费用计算优化，不过这属于另一类统计信息了。