区间 dp

一.什么是区间dp
区间dp就是将题目要求的一大段区间的最优解拆分成许多个小区间，先求每个小区间的最优解，然后通过小区间的最优解来求大区间的最优解
二.核心思想
求解在一个区间上的最优解，那么把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。
代码实现，枚举区间的长度len（从小到大），由小区间逐渐推大区间，最终推到总长度。内层循环小区间的起点，由长度可得出终点，然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。
模板：
for(int len=2;len<=n;len++)//枚举长度 { for(int i=1;i+len-1<=n;i++)//枚举起点 { int l=i,r=i+len-1;//l为左边界，即起点；r为右边界，即终点 f[l][r]=1e8;//赋初值 for(int k=l;k

区间 dp最先出现在Python成神之路。