一、什么是区间DP?
顾名思义：区间DP就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的DP算法。
二、核心思路
既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。板子如下：
1 2 3 4 5 6 7 8 | for(int len = 1;len<=n;len++){//枚举长度 for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n int ends = j+len - 1; for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解 dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something); } } } |
三、朴素区间DP（n³)
例题：石子归并1
（1）N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。
Input
第1行输入一个数N（2 <= N <= 100) 第2 - N+1行每行输入一个数，分别表示N堆石子的数量（1 <= A[i] <= 10000)
Output
输出最小合并代价
Sample
（2）转移方程：
dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);
j~ends堆合并 = 较小的（原来， 分割点i坐部分重量 + 分割点i右边部分重量 + 合并后两堆总重量）
注：可以用sum[j] - sum[i - 1]表示i~j堆的重量！
（3）代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define INF 0x3f3f3fint stone[105];int dp[105][105];int sum[105];int main(){ int n; scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(dp,INF,sizeof(dp)); for(int i =1;i<=n;i++){ scanf("%d",&stone[i]); sum[i] = sum[i - 1] + stone[i];//重量 dp[i][i] = 0; } for(int len = 1;len<=n;len++){//枚举长度 for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n int ends = j+len - 1; for(int i = j;i<ends;i++){//枚举分割点 dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1]);//更新状态 } } } cout<<dp[1][n]<<endl; return 0;} |
四、题目变形（线性变环状）
例题：石子归并2
（1）题意：原题与上面相同，但是石子排列由线性排列变成环状排列，求解。
（2）思路：环状以后合并区间的情况就可以从后往前合并，最后合并完成可能是1~n,2~n~1,3~n~2.....这种n个石子合并的情况。所以我们可以破环成链，将前n-1各元素也放到n后面构成一个线性的环状序列，在对这个序列dp即可
（3）代码：codevs 2102 环状石子归并（求最大值和最小值）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define INF 0x3f3f3fint stone[105];int dpmin[205][205];//最小int dpmax[205][205];//最大int sum[205];int main(){ int n; scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(dpmin,INF,sizeof(dpmin)); memset(dpmax,-1,sizeof(dpmax)); for(int i =1;i<=n;i++){ scanf("%d",&stone[i]); sum[i] = sum[i - 1] + stone[i]; dpmin[i][i] = 0; dpmax[i][i] = 0; } for(int i = 1;i<=n;i++){ sum[i+n] = sum[i+n-1]+stone[i];//展开的n后面的n-1~1重量 dpmin[i+n][i+n] = 0; dpmax[i+n][i+n] = 0; } for(int len = 1;len<=n;len++){//长度还是最大n for(int j = 1;j+len<=2*n;j++){//起点枚举最大到2*n-1,ends<=2*n-1 int ends = j+len - 1; for(int i = j;i<ends;i++){//注意！i<ends！！！因为i=ends时，dp[ends+1][ends]是不成立的！ dpmin[j][ends] = min(dpmin[j][ends],dpmin[j][i]+dpmin[i+1][ends]+sum[ends]-sum[j-1]); dpmax[j][ends] = max(dpmax[j][ends],dpmax[j][i]+dpmax[i+1][ends]+sum[ends]-sum[j-1]); } } } int ansmin = 0xfffffff; int ansmax = -1; for(int i = 1;i<=n;i++){ ansmin = min(ansmin,dpmin[i][i+n-1]);//找1~n,2~n~1,3~n~2....的合并n个堆的中最大和最小的值 ansmax = max(ansmax,dpmax[i][i+n-1]); } cout<<ansmin<<endl; cout<<ansmax<<endl; return 0;} |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程