基本概念
区间类dp是线性dp的扩展，它在分阶段划分问题时，与阶段中元素出现的顺序和由前一段的哪些元素合并而来有很大关系。如状态f[i][j]，它表示以已合并的次数为阶段，以区间左端点 i 为状态，它的值取决于第 i 个元素和第 j 个元素断开的位置 k ，即f[i][k]+f[k][j]的值。
特征：
- 合并：即多个部分进行整合，或者把一个问题分解成多个部分。
- 特征：能把问题分解成两两合并的形式。
- 求解：对整个问题设最优解，枚举合并点，将问题分解成左右两个部分，最后合并左右两个部分的最优值得到原问题的最优值。与分治算法的思想类似。
int dp[N][N];
for(int i=1;
i<=n;
i++)
dp[i][i] = （初始值）;
for(int len=2;
len<=n;
len++){ //区间长度
for(int i=1;
i<=n;
i++){ //枚举起点
int j=i+len-1;
//区间终点
if(j>n) //越界结束
break;
for(int k=i;
k例题
【动态规划 —— 区间DP】经典例题是石子合并、能量项链、凸多边形的划分。
石子合并三种题型
能量项链
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法
- leetcode|递归、动态规划--Leetcode(python)