区间 DP

定义

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

令状态 $f (i, j)$ 表示将下标位置 $i$ 到 $j$ 的所有元素合并能获得的价值的最大值，那么 $f (i, j) = max {f (i, k) + f (k + 1, j) + c o s t}$ ， $c o s t$ 为将这两组元素合并起来的价值。

性质

区间 DP 有以下特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

解释

例题

「NOI1995」石子合并

题目大意：在一个环上有 $n$ 个数 $a_{1}, a_{2}, \dots, a_{n}$ ，进行 $n - 1$ 次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。你需要最大化你的得分。

需要考虑不在环上，而在一条链上的情况。

令 $f (i, j)$ 表示将区间 $[i, j]$ 内的所有石子合并到一起的最大得分。

写出 状态转移方程：$f(i,j)=\max{f(i,k)+f(k+1,j)+\sum_{t=i}^{j} a_t }~(i\le k

本页面最近更新：2024/8/26 01:21:57，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Henry-ZHR, hsfzLZH1, iamtwz, ouuan, Xeonacid, AFObject, billchenchina, Chlero, Early0v0, Enter-tainer, fyulingi, greyqz, ImpleLee, isdanni, ksyx, Menci, OYoooooo, partychicken, shawlleyw, shenshuaijie, StudyingFather, thredreams, Wang Hongtian
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用