区间 DP

教程

区间动态规划是一种通用技巧，用于解决形如“在数组 $A$ 上能够取得的某项指标的最小值或最大值是多少？”的问题。 这类问题具有以下性质：

• 贪心方法看似可行，却会得到错误答案。
• 已知各子数组 $A[l : x]$ 和 $A[y : r]$ 的答案后，可以在 $\mathcal O(r-l)$ 时间内算出子数组 $A[l : r]$ 的答案。
• 互不相交的子数组可以独立地“合并”。
• $N$（即 $A$ 的大小）通常不超过 $500$。

这一技巧基于如下假设：可以“合并”两个子数组 $A[l : x]$ 和 $A[x+1 : r]$， 从而得到 $A[l : r]$ 的一个候选答案。因此，可以遍历所有 $x$，找出 $A[l : r]$ 的最优答案。（注意，必须按长度递增的顺序处理子数组！）

由于共有 $\mathcal O(N^2)$ 个子数组，而处理每个子数组需要 $\mathcal O(N)$ 时间， 使用这一技巧的解法通常具有 $\mathcal O(N^3)$ 的时间复杂度。

我们通过下面的例子来理解区间 DP 的算法。

例1

石子合并