区间DP

区间DP问题

一般来说，区间DP问题都能被转化为多个子区间的合并，在过程中可以枚举合并点将问题分为左右两个部分，从子区间的最优解转移到区间的最优状态上

线性区间合并

https://www.luogu.com.cn/problem/P1775

int m[310];
int dp[310][310];
int pre[310];

void solve(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>m[i];
    for (int i=1;i<=n;i++) pre[i]=pre[i-1]+m[i];
    memset(dp,0x3f,sizeof dp);
    for (int i=1;i<=n;i++) dp[i][i]=0;
    for (int i=2;i<=n;i++){
        for (int j=1;j+i-1<=n;j++){
            for (int k=j;k<j+i-1;k++){
                dp[j][i+j-1]=min(dp[j][i+j-1],dp[j][k]+dp[k+1][i+j-1]+pre[i+j-1]-pre[j-1]);
            }
        }
    }
    cout<<dp[1][n];
}

定义 $dp_{i,j}$ 表示将区间 $[i,j]$ 合并的最小花费

因为在转移到父区间时需要用到子区间的状态，所以我们首先需要从子区间的问题开始解决

for (int i=2;i<=n;i++)

即第一层循环从小到大枚举区间的长度，这样在区间长度变长后才能进行转移

初始化时，已经将区间为 $1$ 的状态进行设置了，这就是状态开始转移的基石，从已知考虑未知

for (int j=1;j+i-1<=n;j++)

第二层循环枚举区间的左端点，右端点可以根据区间长度进行计算，对每一层区间长度，我们都需要遍历所有的子区间，才能得到当前区间长度下的所有状态

for (int k=j;k<j+i-1;k++)

第三层循环枚举区间合并的位置，即将当前的区间 $[j,j+i-1]$ 分解为左右区间 $[j,k],[k+1,j+i-1]$

更新父区间的最优状态，这道题中，状态的转移方程为：

$$ dp_{i,j}={\rm{min}_{k=j}^{j+i-2}}(dp_{j,k}+dp_{k+1,j+i-1}+\sum_{x=j}^{j+i-1} m_x) $$

合并两个区间，需要加上这两堆石子的总数量相同的花费

环形区间合并

https://www.luogu.com.cn/problem/P1880

int a[210];
int pre[210];
int dp[210][210];
int dpp[210][210];

void solve(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) a[i+n]=a[i];
    for (int i=1;i<=2*n;i++) pre[i]=pre[i-1]+a[i];
    memset(dp,0x3f,sizeof dp);
    for (int i=1;i<=2*n;i++) dp[i][i]=0;
    for (int i=2;i<=n;i++){
        for (int j=1;j+i-1<=2*n;j++){
            for (int k=j;k<j+i-1;k++){
                dp[j][j+i-1]=min(dp[j][j+i-1],dp[j][k]+dp[k+1][i+j-1]+pre[i+j-1]-pre[j-1]);
                dpp[j][j+i-1]=max(dpp[j][j+i-1],dpp[j][k]+dpp[k+1][i+j-1]+pre[i+j-1]-pre[j-1]);
            }
        }
    }
    int mx=0,mn=1e9;
    for (int i=1;i<=n;i++){
        mn=min(mn,dp[i][i+n-1]);
        mx=max(mx,dpp[i][i+n-1]);
    }
    cout<<mn<<endl<<mx;
}

对于环状的区间，最暴力的办法就是把两个元素之间断开，然后形成一条链，这样的话时间复杂度会多一层 $O(n)$ ，绝大多数情况下会超时

可以类比字符串最小表示法的破环成链的办法：即将原区间延长两倍，第 $i$ 个元素和 第$i+n$ 个元素相同，再用线性区间上的动态规划求解可以降低复杂度

for (int i=2;i<=n;i++)

即使我们的区间被延长了两倍，但是实际上我们仍然是计算区间长度为 $n$ 的最优解（将共计 $n$ 堆石子合并）

for (int j=1;j+i-1<=2*n;j++)

第二层循环则是枚举延长两倍区间上的所有左端点，余下的操作和线性区间的操作相差不大

形象化的，对于一般的区间DP，状态转移都可以被表示为：

$$ dp_{i,j}={\rm{max}_{k=i}^{j-1}}(dp_{i,k}+dp_{k+1,j}+cost_{k}) $$

其中 $cost_k$ 表示以 $k$ 为合并点需要的费用

特殊区间合并，序列对齐问题

通过状态转移覆盖所有可能对齐的方式，与传统的区间DP基于区间分割的方式不同

https://www.luogu.com.cn/problem/P1140

string a,b;
int dp[110][110];
unordered_map<char,int> mp;

int d[6][6]={
    0,0,0,0,0,0,
    0,5,-1,-2,-1,-3,
    0,-1,5,-3,-2,-4,
    0,-2,-3,5,-2,-2,
    0,-1,-2,-2,5,-1,
    0,-3,-4,-2,-1,0, 
};

void solve(){
    int n,m;
    cin>>n;
    cin>>a;a=' '+a;
    cin>>m;
    cin>>b;b=' '+b;
    memset(dp,-0x3f,sizeof dp);    
    dp[0][0]=0;
    mp['A']=1,mp['C']=2,mp['G']=3,mp['T']=4,mp['-']=5;
    for (int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+d[mp[a[i]]][mp['-']];
    for (int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+d[mp['-']][mp[b[i]]];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+d[mp[a[i]]][mp[b[j]]]);
            dp[i][j]=max(dp[i][j],dp[i][j-1]+d[mp['-']][mp[b[j]]]);
            dp[i][j]=max(dp[i][j],dp[i-1][j]+d[mp[a[i]]][mp['-']]);
        }
    }
    cout<<dp[n][m];
}

这道题目中存在两个不同的区间，这个时候就不能直接套路做题了

定义 $dp_{i,j}$ 表示第一个序列前 $i$ 个元素与第二个序列前 $j$ 个元素的最大匹配值

这是基于区间扩充的思想定义下来的，即考虑两个区间从 $0$ 个元素递推到 $n$ 个元素，核心在于两个序列的逐步对齐

初始化时，当 $dp_{i,j}$ 中任意的 $i,j=0$ 时，只能通过空碱基进行匹配，那么需要前缀和计算出 $dp_{0,j},dp_{i,0}$

然后考虑状态的转移 $i,j$ 对应的碱基存在三类匹配方式：

• $i,j$ 直接匹配，$dp_{i,j}=dp_{i-1,j-1}+d_{i,j}$
• 给 $i$ 匹配空碱基，$dp_{i,j}=dp_{i-1,j}+d_{i,-}$
• 给 $j$ 匹配空碱基，$dp_{i,j}=dp_{i,j-1}+d_{-,j}$

对这三种情况取最优解，注意上述代码中需要初始化 $dp_{i,j}$ 为极小值