一，区间dp
顾名思义，区间dp即为在区间上求解最优值的问题。
其主要的思想就是先对于小区间进行求解，然后再利用小区间的最优解合并求得最大区间的最优解。
话不多说，直接上例题：
典例：(一道非常经典的区间dp的题目)：石子合并
题意：有n堆石子排成一排，每堆石子有一定的数量。现在要将n对石子合并成为一堆。合并的过程中每次只能对相邻的两堆石子合并，每次合并要花费的代价为两堆狮子数量的和，经过n-1次合并后成为一堆，求解出总的代价的最小值。
举例：[4,1,1,4]->[4,2,4]->[4,6]->[10];
2 + 6 + 10 = 18
解题思路：
首先我们考虑最后一次合并，会发现前面一堆是由前k堆合并的，而后面一堆是由后面n-k堆合并在一起的。而代价是石子的总数量。
1，定义状态：设dp[i][j]表示把第 i 堆 ~ 第 j 堆合并的最小花费；sum[i][j]为第 i 堆 ~ 第 j 堆合并的石子数量。
2，转移方程：dp[i][j]=min(dp[i][j],dp[i][k]+dp[i][n-k]+sum[i][j]).
3，求解子状态：递归递推都可以，地推的话可以从区间短的枚举到区间长的。
4，复杂度O(n^3),状态O(n^2)。
代码(部分)：
for(int len=2;len<=n;++len)
for(int l=1;l+len-1<=n;++l)// len=r-l+1 -> r=l+len-1<=n
{
int r=l+len-1;
for(int k=l;k<r;++k)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[l][r]);
}区间dp模板：
1，定义状态：状态为DP(L,R)表示(L~R)的最优解
2，转移方程：枚举区间划分点DP(L,R)=DP(L,K)+DP(K+1,R)+cost(L,R,K)
3,递归或者递推求解：递推为从短区间枚举到长的。
二，例题环节
例题1：划分多边形
解题思路：
（照搬模板）
dp[l][r]表示 l ~ r点构成的多边形剖分最小值。
cost(l ,r ,k)=w[l]*w[k]*w[r].
代码：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> v(n + 1, 0);
for (int i = 1;i <= n;i++)
cin >> v.at(i);
vector<vector<int>> dp(n + 1,vector<int>(n + 1,0));
for(int len=3;len<=n;len++)
for (int l = 1;l + len - 1 <= n;l++)
{
int r = l + len - 1;
if (len == 3)
dp[l][r] = v[l] * v[r] * v[(l + r) / 2];
for (int k = l+1 ;k+1 < r;k++)
dp[l][r] =min(dp[l][k+1]+dp[k+1][r]+v[l]*v[r]*v[k+1], dp[l][k] + dp[k][r] + v[l] * v[r] * v[k]);
}
cout << dp[1][n];
return 0;
}
例题2：最长回文子序列
求一个序列的最长回文子序列的长度
例如：[1,3,2,5,4,2,3,5,1] 答：7
解题思路：
设dp[l][r]表示只考虑 l ~ r 范围的数字，构成的最长回文子序列长度
if(len==1) dp[l][r]=1;
dp[l][r]=max(dp[l][r-1],dp[l+1][r]);
if(a[l]==a[r]) dp[l][r]=max(dp[l][r],dp[l+1][r-1]+2);
代码：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> v(n + 1, 0);
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = 1;i <= n;i++)
cin >> v.at(i);
for(int len=1;len<=n;len++)
for (int l = 1;len + l - 1 <= n;l++)
{
int r = len + l - 1;
if (len == 1)
dp[l][r] = 1;
else
{
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
if (v.at(l) == v[r])
dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
}
}
cout << dp[1][n];
return 0;
}补充：
上述的石子合并里的石子序列是一个链状的序列；
若我们考虑到环状情况，合并的序列可能为：
第 i 堆，第 i+1 堆，第 i+2 堆，......，第 n 堆第 1 堆，.....第 i -1堆；
（环状从一处断开仍为链状。）
假设我们将原来的石子序列复制一遍，（1,2,3,.....,n,1,2,3,......,n),在新的长度为2n的序列上做区间dp，dp[i][i+n-1]的结果即为从i 断开的结果。
复杂度O(n^3)
综合训练：
感兴趣的可以练一练。