# 区间 DP
## 什么是区间 DP?
区间类动态规划是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来由很大的关系。令状态`f(i,j)`表示将下标位置 到 的所有元素合并能获得的价值的最大值,那么`f(i,j)=max\{ f(i,k)+f(k+1,j)+cost\}`,`cost` 为将这两组元素合并起来的代价。
区间 DP 的特点:
**合并** :即将两个或多个部分进行整合,当然也可以反过来;
**特征** :能将问题分解为能两两合并的形式;
**求解** :对整个问题设最优值,枚举合并点,将问题分解为左右两个部分,最后合并两个部分的最优值得到原问题的最优值。
## [洛谷 P1880 石子合并](https://www.luogu.org/problemnew/show/P1880)
考虑不在环上,而在一条链上的情况。
令`f(i,j)`表示将区间`[i,j]`内的所有石子合并到一起的最大得分。
写出 **状态转移方程** :
`f(i,j)=max\{f(i,k)+f(k+1, j) + \sum_{t=i}^ja_t\}(i \leq k<j)`
令 表示 数组的前缀和,状态转移方程变形为
`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)` 的值,而这两个中包含的元素的数量都小于`f( i , 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),...,f(i,n+i-1)`中的最优值,即为最后的答案。时间复杂度`O(n^3)`。
## 核心代码
~~~
for (len = 1; len <= n; len++)
for (i = 1; i <= 2 * n - 1; i++) {
int j = len + i - 1;
for (k = i; k <= j && k <= 2 * n - 1; k++)
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
}
~~~
## 几道练习题
[洛谷 P1063 能量项链](https://www.luogu.org/problemnew/show/P1063)
[洛谷 P1005 矩阵取数游戏](https://www.luogu.org/problemnew/show/P1005)
[洛谷 P4767邮局](https://www.luogu.org/problemnew/show/P4767)
### REFERENCE
\[oi-wiki\][https://oi-wiki.org/dp/interval/#dp](https://oi-wiki.org/dp/interval/#dp)
- 简介
- 零基础快速入门ACM
- C语言快速入门
- C语言快速入门
- C/C++基础
- 输入输出
- 数组和字符串
- 数组
- 字符数组
- 函数和递归
- C++标准容器库(STL)
- Vector
- Map
- Set
- String
- Stack
- Queue
- Priority_queue
- 贪心
- 硬币问题
- 区间调度问题
- 字典序最小问题
- 独木舟问题
- 搜索
- DFS
- BFS
- 剪枝
- 记忆化搜索
- 常用技巧
- 倍增
- 高精度
- 大数加法
- 大数减法
- 大数乘法
- 大数除法
- 大数阶乘
- 输入挂
- 前缀和
- 二分
- 本地预处理
- 尺取
- 枚举
- 坐标离散化
- 分治
- 数列分治
- 树上分治
- 平面分治
- 计算几何
- 凸包
- 点积
- 叉积
- 线段关系
- 皮克定理
- 最近点对
- 数据结构
- 线段树
- 树状数组
- 并查集
- 动态规划
- 基础知识
- 信息学竞赛中的动态规划
- 动态规划初步
- 最长上升子序列(LIS)
- 最长公共子序列(LCS)
- 最大子段和
- 背包问题
- 部分背包
- 0 1 背包
- 完全背包
- 多重背包
- 背包的可行性问题
- 线性DP
- 树形DP
- 区间DP
- 数位DP
- 动态规划优化
- 字符串
- KMP算法
- 拓展KMP
- 字符串Hash
- Manacher算法
- 后缀数组
- Trie树
- 博弈论
- Nim博弈
- Bash博弈
- 斐波那契博弈
- 威佐夫博弈
- SG函数
- 数论
- 整数研究
- 素数判断
- 素数筛选
- 快速幂
- 算数基本定理
- 最大公约数(Gcd)
- 费马小定理
- 扩展欧几里得
- 逆元
- 同余定理
- 组合数学
- 容斥原理
- 抽屉原理
- 卢卡斯(Lucas)
- 卡特兰(Catalan)
- 著名函数
- 欧拉函数
- 莫比乌斯函数
- 线性代数
- 矩阵运算
- 矩阵快速幂
- 图论
- 存图方法
- 邻接矩阵
- 邻接表
- Vector存图
- 链式前向星
- 图的遍历
- 拓扑排序
- 最短路
- Dijkstra算法
- SPFA算法
- Floyed 算法
- 最小生成树
- Prim算法
- Kruskal算法
- 最近公共祖先 (LCA)
- 二分图匹配
- 网络流
- 其他
- 莫队