区间 dp

温家浩 · 2023-08-07 18:54:31 · 个人记录

区间 dp

基本概念与特点

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大关系。

令状态 f_{i,j} 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 f_{i,j}=\max\left\{f_{i,k}+f_{k+1,j}+cost\right\}，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^j_{t=i}a_t\right\}\;(i\le k\le j)。

令 sum_i 表示 a 数组的前缀和，状态转移方程变为：f_{i,j}=\max\left\{f_{i,k}+f_{k+1,j}+sum_j-sum_{i-1}\right\}。

由于计算 f_{i,j} 的值时需要知道所有 f_{i,k} 和 f_{k+1,j} 的值，而这两个中包含的元素的数量都小于 f_{i,j}，所以我们以 len=j-i+1 作为 dp 的阶段，首先从小到大枚举 len，然后枚举 i 的值。根据 len 和 i 用公式计算出 j 的值，然后枚举 k，时间复杂度为 O(n^3)。