区间 DP-未完纪

定义

区间类动态规划是线性动态规划的扩展。分阶段划分问题时，元素出现的顺序，以及当前阶段由前一阶段的哪些元素合并而来，都与问题的求解密切相关。

令状态 $f(i,j)$ 表示合并下标位置 $i$ 到 $j$ 的所有元素可以获得的最大价值，则有：

$f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}$

其中， $cost$ 是合并这两组元素所获得的价值。

性质

区间 DP 有以下特点：

合并：将两个或多个部分整合在一起，也可以反过来理解为拆分。
特征：问题能够分解成可以两两合并的形式。
求解：为整个问题设定最优值，枚举合并点，把问题分为左右两部分，最后合并两部分的最优值，得到原问题的最优值。

解释

例题：石子合并

「NOI1995」石子合并：环上有 $n$ 个数 $a_1,a_2,\dots,a_n$ ，需要进行 $n-1$ 次合并。每次把相邻两堆合并成一堆，获得的分数等于新石子堆的石子总数。目标是最大化总得分。

先考虑石子位于一条链上，而不是环上的情况。

令 $f(i,j)$ 表示将区间 $[i,j]$ 中的所有石子合并到一起的最大得分。状态转移方程为：

$f(i,j)=\max\left\{f(i,k)+f(k+1,j)+\sum_{t=i}^{j}a_t\right\},\quad i\le k<j$

用 $sum_i$ 表示数组 $a$ 的前缀和，方程可写为：

$f(i,j)=\max\{f(i,k)+f(k+1,j)+sum_j-sum_{i-1}\}$

怎样进行状态转移

计算 $f(i,j)$ 时，需要知道各个 $f(i,k)$ 和 $f(k+1,j)$ ；这两个子区间的元素数量都小于原区间。因此，以 $len=j-i+1$ 作为 DP 的阶段：先从小到大枚举 $len$ ，再枚举 $i$ ，由 $len$ 和 $i$ 计算 $j$ ，最后枚举 $k$ 。时间复杂度为 $O(n^3)$ 。

怎样处理环

石子围成一个环而不是一条链，可以采用两种方法。

方法一：枚举断开的位置，把环转化成链。需要枚举 $n$ 次，总时间复杂度为 $O(n^4)$ 。

方法二：把链延长一倍，变成 $2\times n$ 堆，第 $i$ 堆与第 $n+i$ 堆相同。动态规划求解后，在 $f(1,n),f(2,n+1),\dots,f(n,2n-1)$ 中选择最优值作为答案。时间复杂度为 $O(n^3)$ 。

实现

C++

for (len = 2; len <= n; len++)
  for (i = 1; i <= 2 * n - len + 1; i++) {
    int j = len + i - 1;
    for (k = i; k < j; k++)
      f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
  }

Python

for len in range(2, n + 1):
    for i in range(1, 2 * n - len + 2):
        j = len + i - 1
        for k in range(i, j):
            f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1])

几道练习题

原文：OI Wiki：区间 DP。作者：OI Wiki Team 及该页贡献者。正文沿用 CC BY-SA 4.0 与项目附加的 SATA License；本版本整理了中文措辞和版式，并修正两段代码的区间枚举上界，使最后一个长度为 n 的区间也被计算。项目许可声明将代码部分排除在上述正文许可之外，代码的具体许可需遵循其原始声明。

文章版权归作者所有，未经允许请勿转载。

THE END