区间DP

区间DP的定义

区间 \(\text{DP}\)（\(\text{Interval DP}\)），是一类以连续区间 \([l,r]\) 为状态的动态规划。这一类问题通常存在以下的递推结构：

对于任意区间 \([l,r]\)，如果我们能找到一个「点」（例如分割点、最后操作点、配对关系等），使得在我们确定了这个点之后，区间内的决策会自然拆分成若干个更短区间的独立子问题，那或许我们就可以考虑使用区间 \(\text{DP}\) 解决这个问题

区间DP的本质

状态闭包

当我们写出 \(\text{dp[i][j]}\) 时，我们通常要确保以下几个事情：

我们把只考虑子段 \([l,r]\) 当成一个子问题看待。
我们希望这个子问题的最优解，可以通过更短的子段得到。
\(\text{dp[l][r]}\)只依赖区间内的输入与（显式固定的）边界条件，并通过更小区间的状态递推得到，不受区间外决策影响。

基本形式

最常见的状态定义是：

\(\text{dp[l][r]}\) 代表只考虑区间 \([l,r]\) 的最优解（最小代价/最大收益）。

而我们为了保证递推是有效的，我们转移用到的子状态必须来自更短的区间。

区间 \([l,r]\) 的长度为 \(\text{len} = r - l + 1\)，而我们的依赖只依赖于更短的区间，那么按照 \(\text{len}\) 从小到大即可保证正确性：

for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        // 计算 dp[l][r]
    }
}

而具体的边界条件设计，需要根据题目来区分：

如果 \(\text{dp[l][r]}\) 表示把 \([l,r]\) 合并为一个整体的代价，那 \(\text{dp[i][i]}\) 通常设置为 \(0\)，因为单个元素没有合并。
如果 \(\text{dp[l][r]}\) 表示 \([l,r]\) 中某种定义下的最大值，那长度为 \(1\) 的值通常为 \(0\) 或 \(1\)，具体需要根据题目分析。

例题

例题一

这是最常见的一类区间 \(\text{DP}\)，其逻辑是：

区间 \([l,r]\) 的最优方案，一定存在一个我们用小区间拼出来的位置。
在我们拼接之前，两边分别达成了最优解。
因为左右互不相干，我们可以分别取最优解组合起来。

通常形式为：

\[ \text{dp[l][r]} = \min / \max_{l \leq k < r} (\text{dp[l][k]} + \text{dp[k+1][r]} + w(l,k,r)) \]

其中 \(w(l,k,r)\) 代表我们把两个小区间合并成 \([l,r]\) 产生的代价/收益。

例题链接：P1775 石子合并（弱化版）

例题简述：

我们现在有 \(n\) 堆石子，重量分别为 \(w_1,w_2,\dots,w_n\)。每次我们选择相邻的两堆合并，代价为两堆重量的和。问把所有石子合并成一堆的最小总代价。

在这个问题中，每次合并都是合并两个成一个，也就是对于一个大区间的最优解一定是有一个分割点 \(k\) 把大区间分成了两个小区间进行合并。

状态我们设置 \(\text{DP[l][r]}\) 为把区间 \([l,r]\) 合并成同一堆的最小总代价。

而在每一步中，我们具体的代价取决于这个大区间的总重量：

\[ \text{sum}(l,r) \sum_{i=l}^r w_i \]

具体的转移则是：

\[ \text{dp[l][r]} = \min_{l\leq k < r} (\text{dp[l][k]} + dp[k+1][r] + \text{sum}(l,r)) \]

边界则是 \(\text{dp[i][i] = 0}\)。

而对于快速求出 \(\text{sum}(l,r)\) 这一部分，显然我们可以使用前缀和来解决。

例题二

有一些题目如果我们从「分割点」去考虑会难以理解，但是如果我们用最后一次操作的位置去理解就会简单不少。

常见的形式为：

\[ \text{dp[l][r]} = \max_{l < k < r}(\text{dp[l][k]} + \text{dp[k][r]} + w(l,k,r)) \]

其意义是：我们在这个区间内最后操作的位置是 \(k\)，当这个最后的操作发生时， \(k\) 的邻居会是 \(l,r\)，而其代价/收益只取决于 \(l,k,r\)。

例题链接：P1063 [NOIP 2006 提高组] 能量项链

对于这个题而言，如果我们从最后一个操作在哪里入手，整体就会变得很简单：

我们把环切开变成一条链，考虑一个区间 \([l,r]\)，注意这里的区间指的是顶点下标区间。
当我们在合并 \([l,r]\) 这一段的时候，最后一步肯定是选一个操作位置 \(k(l < k < r)\)，形成最后一次合并的三元组 \((l,k,r)\)。
而当最后一步操作发生时，\(l\) 和 \(r\) 已经成为了边界，相邻的关系是固定的，最后一步产生的能量只取决于 \(a_l,a_k,a_r\)，而区间内部则自然分裂成了两个互不干扰的区间问题：\([l,k]\) 和 \([k,r]\)。

这就是这一类题目的特征：选定最后操作点 \(k\) 之后，区间被切成了两块独立的区间，同时代价/收益只依赖于边界。

首先我们把原来的环变成链并且复制一遍，把 \(a[1\dots n]\) 变成 \(a[1\dots 2n]\)，满足 \(a[i+n] = a[i]\)，这样任意长度为 \(n\) 的区间都可以看成原来的环在某个点切开成链。

于是我们可以定义状态 \(\text{dp[l][r]}\) 为在区间 \([l,r]\) 内完成合并能达到的最大能量。

转移的时候我们只需要维护最后一个操作的位置 \(k\)：

\[ \text{dp[l][r]} = \max_{l < k < r} (\text{dp[l][k]} + \text{dp[k][r]} + \text{a[l]} \times \text{a[k]} \times \text{a[r]}) \]

接下来我们需要考虑边界条件如何设置：

当 \(r \leq l + 1\) 时，也就是区间内不足三个点，这个时候无法合并，自然没有收益：

\[ \text{dp[l][l]} = \text{dp[l][l+1]} = 0 \]

例题三

字符串上的区间 \(\text{DP}\) 通常是看端点关系来缩小区间的。

例题链接：B4336 [中山市赛 2023] 永别

状态：\(\text{dp[l][r]}\) 表示 \(\text{s[l...r]}\) 的最长回文子序列长度

转移：

若 \(s[l] = s[r]\)，可把他们作为两端：

\[ \text{dp[l][r]} = \text{dp[l+1][r-1]} + 2 \]

否则至少要丢掉一边：

\[ \text{dp[l][r]} = \max(\text{dp[l+1][r]},\text{dp[l][r-1]}) \]

边界即：\(\text{dp[i][i] = 1}\)。

日志

本页面创建于 2025/12/26 15:16