0x53 区间 DP

到目前为止，我们介绍的线性DP一般从初态开始，沿着阶段的扩张向某个方向递推，直至计算出目标状态。区间DP也属于线性DP中的一种，它以“区间长度”作为DP的“阶段”，使用两个坐标（区间的左、右端点）描述每个维度。在区间DP中，一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来，因此区间DP的决策往往就是划分区间的方法。区间DP的初态一般就由长度为1的“元区间”构成。这种向下划分、再向上递推的模式与某些树形结构，例如第0x43节的线段树，有很大的相似之处。我们把区间DP作为线性DP中一类重要的分支单独进行讲解，将使读者更容易理解下一节树形DP的内容。同时，借助区间DP这种与树形相关的结构，我们也将提及记忆化搜索——其本质是动态规划的递归实现方法。

【例题】石子合并NOI1995/TYVJ1055

有 $N$ 堆石子排成一排，其中第 $i$ 堆石子的重量为 $A_{i}$ 。每次可以选择其中相邻的两堆石子合并成一堆，形成的新石子堆的重量以及消耗的体力都是两堆石子的重量之和。求把全部 $N$ 堆石子合成一堆最少需要消耗多少体力。 $1 \leq N \leq 300$ 。

若最初的第 $l$ 堆石子和第 $r$ 堆石子被合并成一堆，则说明 $l \sim r$ 之间的每堆石子也已经被合并，这样 $l$ 和 $r$ 才有可能相邻。因此，在任意时刻，任意一堆石子均可以用一个闭区间 $[l, r]$ 来描述，表示这堆石子是由最初的第 $l \sim r$ 堆石子合并而成的，其重量为 $\sum_{i=l}^{r} A_i$ 。另外，一定存在一个整数 $k (l \leq k < r)$ ，在这堆石子形成之前，先有第 $l \sim k$ 堆石子（闭区间 $[l, k]$ ）被合并成一堆，第 $k + 1 \sim r$ 堆石子（闭区间 $[k + 1, r]$ ）被合并成一堆，然后这两堆石子才合并成 $[l, r]$ 。

对应到动态规划中，就意味着两个长度较小的区间上的信息向一个更长的区间发生了转移，划分点 $k$ 就是转移的决策。自然地，应该把区间长度len作为DP的阶段。不过，区间长度可以由左端点和右端点表示出，即len=r-l+1。本着动态规划“选择最小的能覆盖状态空间的维度集合”的思想，我们可以只用左、右端点表示DP的状

态。

设 $F[l,r]$ 表示把最初的第 $l$ 堆到第 $r$ 堆石子合并成一堆，需要消耗的最少体力。根据上述分析，容易写出状态转移方程：

初值： $\forall l\in [1,N],F[l,l] = A_l$ ，其余为正无穷。

目标： $F[1,N]$ 。

我们在分组背包最后强调，编程实现动态规划的状态转移方程时，务必分清阶段、状态与决策，三者应该按照从外到内的顺序依次循环。对于 $\sum_{i = l}^{r}A_{i}$ ，可使用前缀和计算。

memset(f, 0x3f, sizeof(f)); // INF
for (int i = 1; i <= n; i++) {
    f[i][i] = 0;
    sum[i] = sum[i-1] + a[i]; // 前缀和
}
for (int len = 2; len <= n; len++) // 阶段
    for (int l = 1; l <= n - len + 1; l++) { // 状态：左端点
        int r = l + len - 1; // 状态：右端点
        for (int k = l; k < r; k++) // 决策
            f[l][r] = min(f[l][r], f[l][k] + f[k+1][r]);
        f[l][r] += sum[r] - sum[l-1];
}

【例题】Polygon IOI1998/FOJ1179

“多边形游戏”是一款单人益智游戏。在游戏开始时，系统给定玩家一个 $N$ 边形，该 $N$ 边形由 $N$ 个顶点和 $N$ 条边构成，每条边连接两个相邻的顶点。在每个顶点上写有一个整数，可正可负。在每条边上标有一个运算符“+”（加号）或“*”（乘号）。

第一步, 玩家需要选择一条边, 将它删除。接下来再进行 $N - 1$ 步, 在每一步中, 玩家选择一条边, 把这条边以及该边连接的两个顶点用一个新的顶点代替, 新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。如下图所示, 就是一盘游戏的过程。

最终，游戏仅剩一个顶点，顶点上的数值就是玩家的得分，上图玩家得零分。

请计算对于给定的 $N$ 边形，玩家最高能获得多少分，以及第一步有哪些策略可以使玩家获得最高得分。 $1 \leq N \leq 50$ ，保证玩家无论如何操作，顶点上的数值均在[-32768,32767]之内。

在枚举第一步删除哪条边后，这道题就与上一题“石子合并”非常相似，仍然是在每一步中对两个相邻的元素做某种运算合成一个。简便起见，我们把被删除的边逆时针方向的顶点称为“第1个顶点”，依此类推。读者容易想到使用 $F[l, r]$ 表示把第 $l$ 到 $r$ 个顶点合成一个顶点后，顶点上的数值最大是多少。

然而，请读者在使用动态规划解决每一道问题时，都时刻牢记动态规划的“三要素”和使用动态规划的“三前提”。把“顶点上的最大数值”作为每一个子问题 $[l, r]$ 的代表信息，不符合动态规划的“最优子结构”性质。因为负数的存在，进行乘法运算时，大区间 $[l, r]$ 合成的顶点的最大数值不能由区间 $[l, k]$ 和区间 $[k + 1, r]$ 合成的两个顶点的最大数值导出——因为区间 $[l, k]$ 和区间 $[k + 1, r]$ 合成的两个顶点的最小数值可能是很小的负数，负负相乘得正，运算结果可能更大。

不过，上面的反例也启发我们，如果把一个区间 $[l, r]$ 能够合成的顶点上的最大和最小数值同时作为子问题 $[l, r]$ 的代表信息，是否满足最优子结构性质？答案是肯定的。最大值的来源只可能是两个最大值相加、相乘，或两个最小值相乘（负负得正）。最小值的来源只可能是两个最小值相加、相乘，或一个最大值与一个最小值相乘（正负得负）。请读者尝试给出完整的证明，这里就不再赘述。

因此，可以设 $F[l,r,0]$ 表示把第 $l$ 到 $r$ 个顶点合成一个顶点后，顶点上的数值最大是多少，设 $F[l,r,1]$ 表示把第 $l$ 到 $r$ 个顶点合成一个顶点后，顶点上的数值最小是多少。枚举区间的划分点 $k$ （决策），状态转移方程如下：

初值： $\forall l\in [1,N],F[l,l,0] = F[l,l,1] = A_l$ ，其余为正或负无穷。

目标： $F[1,N,0]$

上述算法的时间复杂度为 $O(N^{4})$ 。实际上我们还可以进一步优化掉枚举第一步删除哪条边耗费的时间。在游戏最初，我们任意选择一条边删除，然后把剩下的“链”复制一倍接在末尾（以被删除的边逆时针方向的第一个顶点为开头），如下页图所示：

在这个长度为 $2N$ 的“链”上， $\forall i \in [1, N]$ ，把长度为 $N$ 的区间 $[i, i + N - 1]$ 合并成一个顶点，就等价于原游戏的第一步删除第 $i$ 个顶点逆时针一侧的边，然后把剩余的部分合并成一个顶点。因为区间长度是 DP 的阶段，我们只需要对前 $N$ 个阶段进行 DP，每个阶段只有不超过 $2N$ 个状态，总时间复杂度降低为 $O(N^3)$ 。最后的答案是 $\max_{1 \leq i \leq N} \{F[i, i + N - 1]\}$ 。

这种“任意选择一个位置断开，复制形成2倍长度的链”的方法，是解决DP中环形结构的常用手段之一，我们会在0x55节进一步探讨。

【例题】金字塔

虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。并且，每个房间的墙壁都涂有若干种颜色的一种。

探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。

显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次），然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。因为结果可能会非常大，你只需要输出答案对 $10^{9}$ 取模之后的值。

输入文件包含一行, 一个字符串 $S$ , 长度不超过 300, 表示机器人得到的颜色序列。

输出一个整数表示答案。

例如序列“ABABABA”对应5种金字塔结构，最底部是树根。我们认为子树之间是有序的，所以方案3和4是两种不同的方案。如下页图所示。

在0x21节中我们提到过，一棵树的每棵子树都对应着这棵树DFS序中的一个区间。本题中记录的序列虽然不是DFS序，但仍然满足这条性质。因此，这道题目在“树形结构”与“字符串”之间通过“子树”和“区间”建立了联系。结合本节前半部分对区间DP的分析，读者不难想到用 $F[l,r]$ 表示子串 $S[l\sim r]$ 对应着多少种可能的金字塔结构（树形结构）。

接下来我们考虑对区间的划分。以上图中的方案3为例，序列“ABABABA”被分成五个部分：

同理，方案5把序列分成“A|B|A|B|A|B|A”七个部分。也就是说，若子串 $S[l \sim r]$ 对应一棵子树，则 $S[l + 1], S[r - 1]$ 两个字符是进入和离开时产生的。除此之外， $[l, r]$ 包含的每棵更深的子树都对应着一个子问题，会产生 $[l, r]$ 中的一段。相邻两段之间还有途经树根产生的一个字符。因为 $[l, r]$ 包含的子树个数可能不止两个，如果我们像前面的题目一样，采用朴素算法枚举子串 $S[l \sim r]$ 划分点的数量和所有划分点的位置，那么时间复杂度会变得非常高。

读者可能会想到，把子串 $S[l \sim r]$ 分成两部分，每部分可由若干棵子树组成。不过这样可能会产生重复计数。如果每段可以由多棵树树构成，那么划分方案“A|BAB|A|B|A”和“A|B|A|BAB|A”中的“BAB”都能产生“B|A|B”两棵树树，最终归为同一结果——方案5。

实际上，为了解决让计数不重不漏，我们可以只考虑子串 $S[l \sim r]$ 的第一棵子树是由哪一段构成的。枚举划分点 $k$ ，令子串 $S[l + 1 \sim k - 1]$ 构成 $[l, r]$ 的第一棵子树， $S[k \sim r]$ 构成 $[l, r]$ 的剩余部分（其他子树），如下图所示。

如果 $k$ 不相同，那么子串 $S[l + 1 \sim k - 1]$ 代表的子树的大小也不相同，就不可能产生重复计算的结构。于是，我们可以得到状态转移方程：

初值： $\forall l\in [1,N],F[l,l] = 1$ ，其余均为0。目标： $F[1,N]$

这道题告诉我们，对于方案计数类的动态规划问题，通常一个状态的各个决策之间满足“加法原理”，而每个决策划分的几个子状态之间满足“乘法原理”。在设计状态转移方程的决策方式与划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会出现重复问题。在0x5C节我们会进一步探讨计数类DP的相关模型与求解策略。

在具体的程序编写中，区间DP不仅可以用递推（若干循环）来实现，也可以用递归（记忆化搜索）来实现。把子问题的求解过程写成一个函数solve(l,r)，枚举划分点 $k$ ，递归求解solve $(l + 1,k - 1)$ 和solve(k,r)，回溯时把二者的结果相乘，加到solve(l,r）的结果中。在上述过程中，一个区间[l,r]对应的函数solve(l,r）可能会被调用多次，我们可以建立一个全局数组 $F_{\parallel}$ 在第一次计算完solve(l,r）时把结果保存在 $F[l,r]$ 中，之后solve(l,r）再被调用时就可以直接返回 $F[l,r]$ 。这样带有记忆化的搜索就保证了每个区间只会被求解一次，时间复杂度仍然是 $O(N^{3})$

int f[310][310], MOD = 100000000; // 对 MOD 取模

int solve(int l, int r) {
    if (l > r) return 0; // 递归边界
    if (l == r) return 1; // 递归边界
    if (f[l][r] != -1) return f[l][r]; // 记忆化
    f[l][r] = 0;
    for (int k = 1 + 2; k <= r; k++) 
        f[l][r] = (f[l][r] + (long long) solve(l + 1, k - 1) * solve(k, r)) % MOD;
    return f[l][r];
}

memset(f, -1, sizeof(f)); // -1 表示没有被计算过 solve(1, n);