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<j;k++)
      dp[i][j]=max/min(dp[i][j],dp[i][k]+dp[k+1][j]+cost[i][j])
 }

时间复杂度

$O(n^3)$

例题

例题1
例题2