顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
核心思路
既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。栗子如下：
for(int len = 1;len
朴素区间dp（n^3)
例题： [NOI1995] 石子合并
在一个圆形操场的四周摆放 (N) 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 (2) 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 (N) 堆石子合并成 (1) 堆的最小得分和最大得分。
数据的第 (1) 行是正整数 (N)，表示有 (N) 堆石子。
第 (2) 行有 (N) 个整数，第 (i) 个整数 (a_i) 表示第 (i) 堆石子的个数。
输出共 (2) 行，第 (1) 行为最小得分，第 (2) 行为最大得分。
4
4 5 9 4
43
54
(1\leq N\leq 100)，(0\leq a_i\leq 20)。
转移方程：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堆的重量！
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f
int 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
Original: https://www.cnblogs.com/aska00/p/16525346.html
Author: Aska0
Title: 区间dp
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/685767/
转载文章受原作者版权保护。转载请注明原作者出处！