简介

区间动态规划本质上是线性动态规划的一种，但是其独特的思想自称体系，所以被单独提出来成为区间动态规划。

区间动态规划是以区间长度作为DP的阶段，以区间的左右端点作为状态的维度，一个状态通常由被它包含且比它更小的区间状态转移而来。阶段长度、状态左右端点、决策三者按照由外到内的顺序构成三层循环。

区间动态规划的经典运用

例题：石子合并

题目内容

在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。

来源：[洛谷：P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)

题解

设计状态与方程

设$dp_{i,j}$表示将区间$[i,j]$内的所有式子合并到一起的最大的分。

那么我们可以得到以下的转移方程：

$dp_{i,j}=\max_{k\in[i,j)}\{dp_{i,k}+dp_{k+1,j}+\sum^j_{t=i}a_t\}$

其中的$\sum^j_{t=i}a_t$可以使用前缀和的方法来降低复杂度，使用$sum_i$表示前$i$个石子合并到一起的最大得分。所以最终转移方程即为：

$$dp_{i,j}=\max_{k\in[i,j)}\{dp_{i,k}+dp_{k+1,j}+sum_j-sum_{i-1}\}$$

如何进行状态转移

由于计算$dp_{i,j}$的值需要知道所有$dp_{i,k}$和$dp_{k+1,j}$的值，而这两个中包含的元素一定小于$dp_{i,j}$，所以我们以$len=j-i+1$，也就是区间长度作为DP的阶段，从小到大枚举$len$，然后枚举$i$的值，计算出$j$的值再枚举$k$的值。

怎么处理环

根据题目，这些石子都排列在操场上，成环状排列，不能直接的找出一个起点。但是我们可以通过以下两种方法来解决：

1. 枚举分开的位置，将环转化成一个链，由于一共有$n$个可以断环成链的位置，所以要枚举$n$次，最终时间复杂度为$O(n^4)$
2. 随便找到一处位置断开环，然后将这条链延长一倍，从起点进行动态规划，那么计算出来的$dp_{1,n},dp_{2,n+1}, \cdots ,dp_{n-1,2n-2}$这些答案中就包含了所有断链的情况，取其中的最大值即可，最终时间复杂度为$O(n^3)$

很明显，第二种方法时间复杂度更低。

代码

Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
int n,a[1001][1001],dp1[1001][1001],dp2[1001][1001];
int main(){
    read(n);
    for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            dp1[i][j]=1e9;
        }
        dp1[i][i]=0;
    }
    for(int i=1;i<=n;i++){
        read(a[i][i]);
        a[i+n][i+n]=a[i][i];
    }
    for(int i=1;i<=2*n;i++){
        for(int j=i;j<=2*n;j++){
            if(i!=j)
                for(int k=i;k<=j;k++){
                a[i][j]+=a[k][k];
                }
        }
    }
    for(int i=2*n;i>=1;i--){
        for(int j=i+1;j<=2*n;j++){
            for(int k=i;k<j;k++){
                dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]);
                dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]);
            }
            dp1[i][j]+=a[i][j];
            dp2[i][j]+=a[i][j];
        }
    }
    int ans1=1e9,ans2=0;
    for(int i=1;i<=n;i++){
        ans1=min(ans1,dp1[i][i+n-1]);
        ans2=max(ans2,dp2[i][i+n-1]);
    }
    print(ans1);
    enter;
    print(ans2);
    return 0;
}

区间动态规划的简单应用

题目内容

字串$S$长$M$，由$N$个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。

来源：[洛谷：P2890 [USACO07OPEN]Cheapest Palindrome G](https://www.luogu.com.cn/problem/P2890)

题解

设$f_{i,j}$为从$i$到$j$这段区间被修正为回文串的最小花费，$c_{ch,0}$为添加字符$ch$的花费，$c_{ch,1}$为删去字符$ch$的花费，$s$为题目给出的串。为可以用如下几个转移：

用$[i+1,j]$区间转移：这种转移相当于在$[i+1,j]$区间的左边加入一个字符，让[i,j]变为回文的方法为在左边删去该字符或在右边加上该字符，有转移方程：

$$f_{i,j}=\min\{f_{i,j},f_{i+1,j}+\min\{c_{s_i,0},c_{s_i,1}\}\}$$

用$[i,j-1]$区间转移：这种转移相当于在$[i,j-1]$区间的右边加入一个字符，方法同上：

$$f_{i,j}=\min\{f_{i,j},f_{i,j-1}+\min\{c_{s_i,0},c_{s_i,1}\}\}$$

当前区间[i,j]满足$$s_i=s_i$$，直接用$[i+1,j-1]$转移:

$$f_{i,j}=min(f_{i,j},f_{i+1,j-1})$$

代码

Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
int n,m,add[M],del[M],dp[N][N];
char a[M],c[M];
int main(){
    read(n,m);
    for(int i=1;i<=m;i++){
        a[i]=getchar();
    }
    getchar();
    for(int i=1;i<=n;i++){
        c[i]=getchar();
        read(add[(int)c[i]],del[(int)c[i]]);
    }
    for(int i=1;i<=m;i++){
        dp[i][i]=0;
    }
    for(int len=2;len<=m;len++){
        for(int i=1;i<=m-len+1;i++){
            int j=i+len-1;
            if(a[i]==a[j]){
                dp[i][j]=dp[i+1][j-1];
            }
            else{
                int delval=Min(dp[i+1][j]+del[(int)a[i]],dp[i][j-1]+del[(int)a[j]]);
                int addval=Min(dp[i+1][j]+add[(int)a[i]],dp[i][j-1]+add[(int)a[j]]);
                dp[i][j]=Min(delval,addval);
            }
        }
    }
    print(dp[1][m]);
    return 0;
}