DP 优化

单调队列优化 DP

单调队列在 DP 中优化的基本应用，是对这样一类 DP 状态转移方程进行优化

$dp[i] = \min\{dp[j] +a[i]+a[j]\},L(i) \le j \le R(i)$

方程的特点是其中关于 $i$ 的项 $a[i]$ 和关于 $j$ 的项 $a[j]$ 是独立的。 $j$ 被限制在窗口 $[L(i),R(i)]$ 内

如果单纯的枚举 $j$ ，复杂度为 $O(n^2)$ 但是使用单调队列优化可以到 $O(n)$

我们假设 $j$ 的活动窗口为 $i-k \le j \le i$ ，那么发现 $i$ 和 $i+1$ 所对应的 $j$ 有很大一部分重叠，产生了重复计算，如果我们能减少这些重复计算就能优化复杂度

在 $i$ 增大的过程中，我们用一个单调队列来维护决策 $dp[j]+a[j]$ 的最小值，因为对于 $i$ 来说 $a[i]$ 可以看成是常量

考虑维护 $dp[j]+a[j]$ 的最小值，如果一个 $j$ 比 $j'$ 更靠右并且 $dp[j]+a[j] < dp[j']+a[j']$ 那么 $j'$ 就没有存在的意义了，因为 $j$ 能往后拓展的 $i$ 要比 $j'$ 多

那么如何取得答案？如果这是一个单调递增的队列，那就取头，如果头部的节点不合法，在 $j$ 的窗口外，那就再取一个，直到合法为止

四边形不等式优化 DP

一些常用的区间 DP 问题的状态转移方程为：

$dp[i][j]=\min_{k=i}^{j-1}\{dp[i][k]+dp[k+1][j]+w[i][j]\}$

$w[i][j]$ 满足以下几个性质时：

1. 四边形不等式：设 $a\le b\le c\le d$ 有， $w[a,d]+w[b,c]\ge w[a,c]+w[b,d]$，包含和 $\ge$ 交叉和
2. 单调性：设 $i \le i' \le j' \le j$ 满足：$w[i][j] \le w[i'][j']$

DP 转移的最后一层 $k$ 可以减小范围

for (int len = 1; len <= n; len ++)
	for (int i = 1; i + len - 1 <= n; i ++){
		int j = i + len - 1;
		for (int k = p[i][j-1]; k <= p[i + 1][j]; k ++){
			if(dp[i][j] > dp[i][k] + dp[k + 1][j] + w[i][j]){
				dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j];
				p[i][j] = k;
			}
		}
	}

其中 $p[i][j]$ 表示 $dp[i][j]$ 的决策点