https://blog.csdn.net/SunPeishuai/article/details/81772406
所谓区间dp,就是在一个区间上进行的dp， 一般通过将大区间分割成小区间进行dp。
区间型动态规划，又称为合并类动态规划，是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的区间中哪些元素合并而来有很大的关系。
区间dp的特征：给的数据为一条链或者一个环（环形dp）
区间动归状态转移方程及一般动规过程：
for k:=1 to n-1 do //区间长度
for i:=1 to n-k do //区间起点
for j:=i to i+k-1 do //区间中任意点
dp[i,i+k]:=max{dp[i,j] + dp[j+1,i+k] + a[i,j] + a[j+1,i+k]};
1. 状态转移方程字面意义：寻找区间dp[i,i+k]的一种合并方式dp[i,j] + dp[j+1,i+k]，使得其值最大或最小。
2. 区间长度k必须要放到第一层循环，来保证方程中状态dp[i,j]、dp[j+1,i+k]值在dp[i,i+k]之前就已计算出来。
3. 其中a[i,j]+a[j+1,i+k]可以不要，也可以灵活多变，指的是合并区间时产生的附加值。
https://blog.csdn.net/my_sunshine26/article/details/77141398
https://blog.csdn.net/iteye_19603/article/details/82517584
所谓区间dp,就是在一个区间上进行的dp， 一般通过将大区间分割成小区间进行dp。
区间型动态规划，又称为合并类动态规划，是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的区间中哪些元素合并而来有很大的关系。
区间dp的特征：给的数据为一条链或者一个环（环形dp）
区间动归状态转移方程及一般动规过程：
for k:=1 to n-1 do //区间长度
for i:=1 to n-k do //区间起点
for j:=i to i+k-1 do //区间中任意点
dp[i,i+k]:=max{dp[i,j] + dp[j+1,i+k] + a[i,j] + a[j+1,i+k]};
1. 状态转移方程字面意义：寻找区间dp[i,i+k]的一种合并方式dp[i,j] + dp[j+1,i+k]，使得其值最大或最小。
2. 区间长度k必须要放到第一层循环，来保证方程中状态dp[i,j]、dp[j+1,i+k]值在dp[i,i+k]之前就已计算出来。
3. 其中a[i,j]+a[j+1,i+k]可以不要，也可以灵活多变，指的是合并区间时产生的附加值。
https://blog.csdn.net/my_sunshine26/article/details/77141398
区间dp一般由小区间推出大的区间：
区间DP，顾名思义是在区间上DP，它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。
下面给出区间DP最简单形式的伪代码(具体要根据题目修改)
//mst(dp,0) 初始化DP数组
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<j;k++) //枚举分割点，构造状态转移方程
{
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
}
}
1 for循环
2 是搜索+记忆
