动态规划5.2-区间动态规划

一、区间动态规划

区间动态规划是动态规划中的一类题，下面先引入几个题目，最后总结一下此类问题的相关解题思路

二、例题

1.[Daimayuan Online Judge.石子合并]

题目描述

有 \(n\) 堆石子排成一排，第 \(i\) 堆石子有 \(a_i\) 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

输入格式

第一行一个数字 \(n\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\)。

输出格式

一行一个整数，表示答案。

输入样例

3
1 2 3

输出样例

9

数据范围

对于所有数据，保证 \(1≤n,a_i≤500\)。

解题思路

对于第 \(i\) 和 \(i+1\) 堆石子合并，代价为 \(a_i+a_{i+1}\)，\(1≤i<n\)。因此需要预处理前缀和

• 状态表示：\(f[i][j]\) 表示合并 \(i\) 到 \(j\) 堆石子的代价，需要求解最小值
• 状态计算：合并第 \(i\) 到 \(j\) 堆石子，可分为合并 \(f[i][k]\) 和 \(f[k+1][j]\)，\(k\in[i,j)\)，故 \(f[i][j]=f[i][k]+f[k+1][j]+a_i+a_{i+1}+...+a_{j}\)，枚举分界点 \(k\) 求解最小值

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n;
int a[N], s[N];
int f[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            f[l][r] = 0x3f3f3f3f;
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}

2.[Daimayuan Online Judge.括号序列]

题目描述

给定一个长度为 \(n\) 的字符串 \(s\)，字符串由 \((, ), [, ]\) 组成，问其中最长的合法子序列有多长？也就是说，我们要找到最大的 \(m\)，使得存在 \(i_1,i_2,…,i_m\) 满足 \(1≤i_1<i_2<⋯<i_m≤n\) 并且 \(s_{i_1}s_{i_2}…s_{i_m}\) 是一个合法的括号序列。
合法的括号序列的定义是：

• 空串是一个合法的括号序列。
• 若 \(A\) 是一个合法的括号序列，则 \((A), [A]\) 也是合法的括号序列。
• 若 \(A, B\) 都是合法的括号序列，则 \(AB\) 也是合法的括号序列。

输入格式

第一行一个数字 \(n\)。
接下来一行，一个长度为 \(n\) 的字符串 \(s\)。

输出格式

一行一个整数，表示答案。

输入样例

10
]]][()]])[

输出样例

4

数据范围

对于所有数据，保证 \(1≤n≤500\)。

解题思路

• 状态表示：\(f[i][j]\) 表示 \(i\) 到 \(j\) 的合法括号序列，属性值为长度
• 状态计算：根据合法括号序列的定义，对于 \(f[i][j]\)，如果 \(s_i=s_j\)，则 \(f[i][j]=f[i++1][j-1]+2\)，否则 \(f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j+1]))\)；另外，根据 “若 \(A, B\) 都是合法的括号序列，则 \(AB\) 也是合法的括号序列”，可以枚举分界点，进行括号序列的拼接，即 \(f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]),k\in[i,j)\)，且这种情况可以包含 \(s_i\neq s_j\) 这种情况，减少代码量

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n;
char s[N];
int f[N][N];

int main() {
    scanf("%d%s", &n, s + 1);
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            if (s[l] == '[' && s[r] == ']' || s[l] == '(' && s[r] == ')')
                f[l][r] = f[l + 1][r - 1] + 2;
            for (int k = l; k < r; k++)
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}

3.[Daimayuan Online Judge.石子合并2]

题目描述

有 \(n\) 堆石子围成一个圈，第 \(i\) 堆石子有 \(a_i\) 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

输入格式

第一行一个数字 \(n\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\)。

输出格式

一行一个整数，表示答案。

输入样例

3
1 3 2

输出样例

9

数据范围

对于所有数据，保证 \(1≤n≤250,1≤a_i≤500\)。

解题思路

典型的环型区间动态规划问题，此类题目可以将序列重复一遍，也就是令 \(a_i=a_{i+n}\)，这样当作一个链式区间动态规划问题进行求解，这样的话先求解整个的区间结果，最后取其中的一部分即可，结合本题目就是，先求解 \(a_1\) 到 \(a_{2n}\) 的最小代价，然后取其中长度为 \(n\) 的合并代价取最小值

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n;
int a[N], s[N];
int f[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++)
        s[i] = s[i - 1] + a[i];
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= 2 * n; i++) {
            int l = i, r = i + len - 1;
            f[l][r] = 0x3f3f3f3f;
            for (int k = i; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        ans = min(ans, f[i][i + n - 1]);
    printf("%d\n", ans);
    return 0;
}

三、总结

区间动态规划的问题的求解还是比较有套路的，基本状态表示都是二维表示区间的左右端点，当然某些问题可能涉及到最后在哪个端点处，这样就需要额外考虑一维，用 \(0\) 和 \(1\) 两种状态来区分。