c++算法--区间dp

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。

合并：即将两个或多个部分进行整合。
特征：能将问题分解成为两两合并的形式。
求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部分，最后将左右两个部分的最优值进行合并得到原问题的最优值。

既然要求解在一个区间上的最优解，那么我们把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。

所以在代码实现上，我们可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。

for (int len=2;len<=n;len++)
  for(int i=1;i+len-1<=n;i++){
    int j=i+len-1;
    //特殊情况判断，如无则省略
    if() dp[i][j]=...
    //枚举区间分割点
    for(int k=i;k 
时间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         3
        
       
       
        )
       
      
      
       O(n^3)
      
     
    O(n3)
 
例题 
例题1
 例题2