浅谈区间DP

· · 算法·理论

前言

第一次发这种类型的文章，心里有点紧张。

正文

DP 类型有很多，背包 DP，数位 DP，多线程 DP，棋盘 DP 等等，今天我们讲的是区间 DP。

区间 DP 是处理区间分段处理相关问题的 DP，枚举区间的长度，再枚举起点，枚举区间中间取的断点，将断点左右区间合并的结果取最小/大值，转移方程就显而易见了（以最小值为例），DP 状态就是从 l \sim r 这段区间的所要求的值（按题面要求）：

dp_{l,r}=\min\{dp_{l,k}+dp_{k+1,r}\}

其中，l 为区间起点，r 为区间终点，k 为断点，k 满足 l \le k < r。

这里描述的是大多数情况，其他情况需要随机应变。

下面我们来看几道题目。

练习题

P1063 [NOIP 2006 提高组]能量项链

这里环的问题可能有人不会，这里我们就将他断环成链，原本长度为 n 的环形序列改换为 2 \times n 的线性序列，最后面 n 个就是从前面复制过去的，现在思路就比较清晰了吧，后面就是普通模板了。

#include<bits/stdc++.h>
using namespace std;
int n , a[215] , dp[215][215] , maxn;
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        a[i + n] = a[i];
    }
    for(int len = 2;len <= n + 1;len++){
        for(int l = 1;l + len - 1 <= 2 * n;l++){
            int r = l + len - 1;
            for(int i = l + 1;i < r;i++)dp[l][r] = max(dp[l][r] , dp[l][i] + dp[i][r] + a[l] * a[r] * a[i]);
        }
    }
    for(int i = 1;i <= n;i++)maxn = max(maxn , dp[i][i + n]);
    cout << maxn;
    return 0;
}

P1775 石子合并（弱化版）

板子题，只是这里需要存下前缀和，以处理合并时区间和的问题，这里不过多赘述。

#include<bits/stdc++.h>
using namespace std;
int n , a[305] , dp[305][305] , s[305];
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    memset(dp , 0x3f , sizeof(dp));
    for(int i = 0;i <= n;i++)dp[i][i] = 0;
    for(int len = 2;len <= n;len++){
        for(int l = 1;l + len - 1 <= n;l++){
            int r = l + len - 1;
            for(int i = l;i < r;i++){
                dp[l][r] = min(dp[l][i] + dp[i + 1][r] , dp[l][r]);
            }
            dp[l][r] += s[r] - s[l - 1];
        }
    }
    cout << dp[1][n];
    return 0;
}

P1880 [NOI1995] 石子合并

与第一道练习题相似，同样是断环成链，不过多赘述。

#include<bits/stdc++.h>
using namespace std;
int n , a[205] , s[205] , dp[205][205] , dp2[205][205] , minn = 1e9 , maxn;
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for(int i = n + 1;i <= 2 * n;i++){
        a[i] = a[i - n];
        s[i] = s[i - 1] + a[i];
    }
    memset(dp , 0x3f , sizeof(dp));
    for(int i = 0;i <= 2 * n;i++)dp[i][i] = 0;
    for(int i = 2;i <= 2 * n;i++){
        for(int l = 1;l + i - 1 <= 2 * n;l++){
            int r = l + i - 1;
            for(int j = l;j < r;j++)dp[l][r] = min(dp[l][j] + dp[j + 1][r] , dp[l][r]);
            dp[l][r] += s[r] - s[l - 1];
        }
    }
    for(int i = 2;i <= 2 * n;i++){
        for(int l = 1;l + i - 1 <= 2 * n;l++){
            int r = l + i - 1;
            for(int j = l;j < r;j++)dp2[l][r] = max(dp2[l][j] + dp2[j + 1][r] , dp2[l][r]);
            dp2[l][r] += s[r] - s[l - 1];
        }
    }
    for(int i = 1;i + n - 1 <= 2 * n;i++){
        int j = i + n - 1;
        minn = min(minn , dp[i][j]);
        maxn = max(maxn , dp2[i][j]);
    }
    cout << minn << '\n' << maxn;
    return 0;
}

P4170 [CQOI2007] 涂色

上了一点难度了，这题我们分类讨论一下。

dp_{l,r} = \begin{cases} l=r & 1\\ s_l=s_r & \min\{dp_{l,r-1},dp_{l+1,r}\}\\ l \ne r 且 s_l \ne s_r & \min\{dp_{l,k}+dp_{k+1,r}\} \end{cases}

第一个就是区间长度为 1，只用涂一次色。

第二个是前后字符相等，就只会从比它的长度少一的区间过来。

第三个就不用多说了，板子。

#include<bits/stdc++.h>
using namespace std;
string s;
long long dp[55][55];
int main(){
    cin >> s;
    memset(dp , 0x7f , sizeof(dp));
    for(int len = 0;len < s.size();len++){
        for(int l = 0;l < s.size() - len;l++){
            int r = l + len;
            if(l == r)dp[l][r] = 1;
            else if(s[l] == s[r])dp[l][r] = min(dp[l][r - 1] , dp[l + 1][r]);
            else {
                for(int i = l;i < r;i++)dp[l][r] = min(dp[l][r] , dp[l][i] + dp[i + 1][r]);
            }
        }
    }
    cout << dp[0][s.size() - 1];
    return 0;
}

总序

那么这一期讲解就到这了，有什么错误大佬可以指点指点。