定义

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么

f(i,j)=max⁡{f(i,k)+f(k+1,j)+cost}f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}

cost 为将这两组元素合并起来的代价。

性质

区间 DP 有以下特点：

  1. 合并：即将两个或多个部分进行整合，当然也可以反过来；
  2. 特征：能将问题分解为能两两合并的形式；
  3. 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

典型例题

石子合并1

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

试设计一个算法，计算出将 N 堆石子合并成一堆的最小得分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int maxN = 305;

int arr[maxN];
int prefix[maxN];
int dp[maxN][maxN];

int main() {
    std::ios::sync_with_stdio(false);
    int N;
    cin >> N;
    memset(dp, 0x3f, sizeof(dp));
    prefix[0] = 0;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        prefix[i] = prefix[i - 1] + arr[i];
    }
    for (int i = 1; i <= N; i++) dp[i][i] = 0, dp[i][i + 1] = arr[i] + arr[i + 1];
    for (int k = 2; k < N; k++) {
        for (int i = 1; i + k <= N; i++) {
            int j = i + k;
            for (int t = i; t < j; t++) {
                dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j] + prefix[j] - prefix[i - 1]);
            }
        }
    }
    cout << dp[1][N] << endl;
}

石子合并2

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int maxN = 205;

int arr[maxN];
int prefix[maxN];
int dpMax[maxN][maxN];
int dpMin[maxN][maxN];

int main() {
    std::ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        arr[i + N] = arr[i];
    }
    prefix[0] = 0;
    for (int i = 1; i <= 2 * N; i++) {
        prefix[i] += prefix[i - 1] + arr[i];
    }
    memset(dpMax, 0, sizeof(dpMax));
    memset(dpMin, 0x3f, sizeof(dpMin));
    for (int i = 0; i < 2 * N; i++) dpMax[i][i] = 0, dpMin[i][i] = 0;
    for (int k = 1; k < N; k++) {
        for (int i = 1; i + k <= 2 * N; i++) {
            int j = i + k;
            for (int t = i; t < j; t++) {
                dpMax[i][j] = max(dpMax[i][j], dpMax[i][t] + dpMax[t + 1][j] + prefix[j] - prefix[i - 1]);
                dpMin[i][j] = min(dpMin[i][j], dpMin[i][t] + dpMin[t + 1][j] + prefix[j] - prefix[i - 1]);
            }
        }
    }
    int ansMax = 0;
    int ansMin = INT_MAX;
    for (int i = 1; i <= N; i++) {
        ansMax = max(ansMax, dpMax[i][i + N - 1]);
        ansMin = min(ansMin, dpMin[i][i + N - 1]);
    }
    cout << ansMin << endl;
    cout << ansMax << endl;
}

石子合并3

有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。

思路分析

n 大于 1 时若想将 n 堆石子合并为 1 堆，我们首先准备好不同的 k 堆，因此可以用 d[l][r][t] 描述这个状态，表示将 [l,r] 合并为 t (1≤t≤k) 堆的最低成本。与 k=2 时的思考方式一致，我们考虑一个分界点 p (l≤p<r)，令 [l,p] 合并为 1 堆，再令 [p+1,r] 合并为 t−1 堆，这样就可以将问题拆分为两个子问题进行求解。

区间dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    static constexpr int inf = 0x3f3f3f3f;
public:
    int mergeStones(vector<int>& stones, int k) {
        if ((stones.size() - 1) % (k - 1) != 0) return -1;
        vector dp(stones.size(), vector(stones.size(), vector(k + 1, inf)));
        vector sum(stones.size() + 1, 0);
        for (int i = 0; i < stones.size(); i++) {
            sum[i + 1] = sum[i] + stones[i];
            dp[i][i][1] = 0;
        }
        for (int len = 2; len <= stones.size(); len++) {
            for (int i = 0; i + len - 1 < stones.size(); i++) {
                int j = i + len - 1;
                for (int t = 2; t <= k; t++) {
                    for (int p = i; p < j; p += k - 1) {
                        dp[i][j][t] = min(dp[i][j][t],
                                          dp[i][p][1] + dp[p + 1][j][t - 1]);
                    }
                }
                dp[i][j][1] = min(dp[i][j][1], dp[i][j][k] + sum[j + 1] - sum[i]);
            }
        }
        return dp[0][stones.size() - 1][1];
    }
};

状态优化

在方法一中，我们用 d[l][r][t] 表示将区间 [l,r] 的石头堆合并为 t 堆的最小成本，这里 t 的范围是 [1,k]。事实上，对于一个固定的区间 [l,r]，最终合并到小于 k 堆时的堆数是固定的。

我们每次合并都会减小 k−1 堆，初始时 [l,r] 的堆数是 r−l+1，合并到不能合并时的堆数为 (r−l)mod  (k−1)+1。所以我们可以直接用 d[l][r] 表示将区间 [l,r] 合并到不能为止时的最小成本。它本质上是通过忽略方法一中一定无解的状态，加快求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    static constexpr int inf = 0x3f3f3f3f;
public:
    int mergeStones(vector<int>& stones, int k) {
        if ((stones.size() - 1) % (k - 1) != 0) return -1;
        vector dp(stones.size(), vector(stones.size(), inf));
        vector sum(stones.size() + 1, 0);
        for (int i = 0; i < stones.size(); i++) {
            sum[i + 1] = sum[i] + stones[i];
            dp[i][i] = 0;
        }
        for (int len = 2; len <= stones.size(); len++) {
            for (int i = 0; i + len - 1 < stones.size(); i++) {
                int j = i + len - 1;
                for (int p = i; p < j; p += k - 1) {
                    dp[i][j] = min(dp[i][j], dp[i][p] + dp[p + 1][j]);
                }
                if ((len - 1) % (k - 1) == 0) {
                    dp[i][j] += sum[j + 1] - sum[i];
                }
            }
        }
        return dp[0][stones.size() - 1];
    }
};

能量环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int maxN = 205;

int arr[maxN];
int dp[maxN][maxN];

int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        arr[i + N] = arr[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int len = 2; len <= N; len++) {
        for (int i = 1; i + len - 1 <= 2 * N; i++) {
            int j = i + len - 1;
            for (int t = i; t < j; t++) {
                dp[i][j] = max(dp[i][j], dp[i][t] + dp[t + 1][j] + arr[i] * arr[t + 1] * arr[j + 1]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, dp[i][i + N - 1]);
    }
    cout << ans << endl;
}

合唱队

看了题目发现要用区间 dp，为什么?

我们发现区间 dp 有一个性质——大区间包含小区间，这道题就符合这样的一个性质。

所以我们要用区间 dp 来解决这道题。 如何设计状态 那么我们要怎么设计状态，我们想，每给人进入队伍里，只有 2 种可能： 从左边加入; 从右边进入。 所以我们的状态是有3个数： F(i,j,0) 表示的是第 i 人从左边进来的方案数； F(i,j,1) ​ 表示的是第 j 人从右边进来的方案数。

那么状态转移方程就出来了：

1
2
3
4
if (a[i] < a[i + 1]) f[i][j][0] += f[i + 1][j][0];
if (a[i] < a[j])     f[i][j][0] += f[i + 1][j][1];
if (a[j] > a[i])     f[i][j][1] += f[i][j - 1][0];
if (a[j] > a[j - 1]) f[i][j][1] += f[i][j - 1][1];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxN = 1005;
const int p = 19650827;
int arr[maxN];
int dp[maxN][maxN][2];

int main() {
    memset(dp, 0, sizeof(dp));
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i], dp[i][i][0] = 1;
    for (int len = 2; len <= N; len++) {
        for (int i = 1; i + len - 1 <= N; i++) {
            int j = i + len - 1;
            if (arr[i] < arr[i + 1]) dp[i][j][0] += dp[i + 1][j][0] % p;
            if (arr[i] < arr[j]) dp[i][j][0] += dp[i + 1][j][1] % p;
            if (arr[j] > arr[j - 1]) dp[i][j][1] += dp[i][j - 1][1] % p;
            if (arr[j] > arr[i]) dp[i][j][1] += dp[i][j - 1][0] % p;
        }
    }
    cout << (dp[1][N][0] + dp[1][N][1]) % p << endl;
}

Zuma

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int maxN = 505;

int arr[maxN];
int dp[maxN][maxN];

int main() {
    memset(dp, 0x3f, sizeof(dp));
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i], dp[i][i] = 1;
    for (int i = 1; i < N; i++)
        if (arr[i] == arr[i + 1]) dp[i][i + 1] = 1;
        else dp[i][i + 1] = 2;
    for (int len = 3; len <= N; len++) {
        for (int i = 1; i + len - 1 <= N; i++) {
            int j = i + len - 1;
            if (arr[i] == arr[j]) dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
            for (int t = i; t < j; t++) {
                dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]);
            }
        }
    }
    cout << dp[1][N] << endl;
}

石子合并4

前置知识: GarsiaWachs算法

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

试设计一个算法，计算出将 N 堆石子合并成一堆的最小得分。注意 N<=40000

1