DP 优化

单调队列优化 DP

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

方程的特点是其中关于 $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^{\prime }$ 更靠右并且 $dp[j]+a[j]<dp[j^{\prime }]+a[j^{\prime }]$ 那么 $j^{\prime }$ 就没有存在的意义了，因为 $j$ 能往后拓展的 $i$ 要比 $j^{\prime }$ 多

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

四边形不等式优化 DP

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

$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^{\prime }\le j^{\prime }\le j$ 满足：$w[i][j]\le w[i^{\prime }][j^{\prime }]$

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]$ 的决策点