决策单调性
决策单调性一般用于最优性问题当中，即一个状态只能从一个最优的状态转移，该最优状态称之为最优点。决策单调性就是指最优点随 dp 转移单调移动。
一般如果能够将 dp 转移方程写成如下形式：
\(f_i = \min / \max{f_j + w(j, i)} (j < i)\)
且函数 \(w(j, i)\) 满足一些特殊的性质时，我们可以利用决策的单调性进行优化。
四边形不等式
下文讨论均以求最小值为例，若求最大值需要将不等式取反。
- 区间包含单调性
决策单调性一般用于最优性问题当中，即一个状态只能从一个最优的状态转移，该最优状态称之为最优点。决策单调性就是指最优点随 dp 转移单调移动。
一般如果能够将 dp 转移方程写成如下形式：
\(f_i = \min / \max{f_j + w(j, i)} (j < i)\)
且函数 \(w(j, i)\) 满足一些特殊的性质时，我们可以利用决策的单调性进行优化。
下文讨论均以求最小值为例，若求最大值需要将不等式取反。