CSP-J/S 复赛算法 区间动态规划

前言

在算法竞赛中，动态规划（DP）是一种常见且强大的解题方法。而区间动态规划作为动态规划的一个变种，主要应用于需要处理区间问题的场景，如括号匹配问题、石子合并问题、矩阵连乘等。区间DP的核心思想是在处理一个问题时，通过划分区间并递归地处理子问题，最终通过组合子问题的最优解来解决整个问题。

区间DP的难点在于如何定义状态和转移方程，通常我们需要确定合适的状态表示方式，例如以区间的左右边界作为状态变量。通过遍历区间长度以及起点和终点，逐步缩小问题的规模，从而构建全局最优解。

本文旨在介绍区间动态规划的基本思想和常见应用场景，帮助读者理解这一重要的算法思想，并提供在竞赛中灵活运用该技术的思路。

区间动态规划

什么是区间动态规划？

区间动态规划是一种用来解决问题的方法，特别是那些涉及到一段时间或一段空间（比如数组或字符串）的问题。想象一下，你有一条长长的绳子，可以把它分成很多段。每一段都有它自己的特性，比如长度、颜色或者价格。我们想要找到一种最好的分割方式，使得我们的目标（比如总长度或总价格）最大。

区间动态规划与线性动态规划的关系

• 线性动态规划 是处理问题的一种方法，通常是用来解决一维的问题，比如一个数组。我们在这里是考虑“前一个”状态，逐步计算出每个状态的结果。

• 区间动态规划 则是在线性动态规划的基础上，处理更多维度的问题，通常涉及到多个区间或者子数组。比如，我们可能想要在一个数组中找出最优的连续子数组的和，或者在一个字符串中找出最优的子串。

简单来说，区间动态规划是在更复杂的问题上使用动态规划的技巧。它更像是在一个长长的队伍中找出最好的小组，而线性动态规划则是解决每个人的排名问题。

区间动态规划的应用

区间动态规划可以用在很多场合，比如：

1. 最优分割问题：我们可以把一个长长的绳子切成若干段，计算不同的切割方式来找到总价值最大的方案。

2. 字符串的最优组合：在编程中，可能需要将一个字符串的某些部分组合起来，找出最优的组合方式，比如拼写成某个特定的单词。

3. 矩阵链乘法：在数学中，有些矩阵相乘时，可以通过选择不同的乘法顺序来减少计算的复杂度。我们可以利用区间动态规划来找出最好的乘法顺序。

通过区间动态规划，我们可以更高效地解决一些复杂的问题，让我们在编程中更轻松地找到最佳解。

区间动态规划的模板

for(int len = 1; len <= n; len++){ //枚举每个小区间
	for(int j = 1; j+len-1 <= n; j++){ //枚举起点，ends <= n
		int ends = j+len - 1;
		for(int i = j; i < ends; i++){ //枚举分割点，更新小区间最优解
			dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
		}
	}
}

模板解释

这个模板的目的是帮助我们找到在某个区间内的最优解，比如在一个数组中找出某段元素的最小值、最大值或其他属性。让我们一步步来看看每一部分。

for(int len = 1; len <= n; len++){ // 枚举每个小区间

1. 外层循环 len：这个循环是在说“我想要考虑所有可能长度的小区间”。从1开始，到 n 结束（n 是整个数组的长度）。也就是说，我们从长度为1的小区间开始，逐渐增大到长度为 n 的整个区间。

for(int j = 1; j + len - 1 <= n; j++){ // 枚举起点，ends <= n

2. 中层循环 j：这个循环是用来选择每个小区间的起点（j）。它从1开始，每次向右移动一个位置。j + len - 1 是区间的结束点（ends），我们确保这个结束点不会超过 n，这样就不会越界。

int ends = j + len - 1;

3. 定义 ends：这里我们定义了这个小区间的结束点（ends），它是由起点 j 和长度 len 计算得出的。

for(int i = j; i < ends; i++){ // 枚举分割点，更新小区间最优解

4. 内层循环 i：这个循环是用来找出在当前区间（从 j 到 ends）中可以进行的分割点（i）。我们会在这个区间中尝试将其分成两个部分，这样就可以计算出两部分的最优解。

dp[j][ends] = min(dp[j][ends], dp[j][i] + dp[i + 1][ends] + something);

5. 更新最优解：在这一行代码中，我们计算并更新当前小区间（从 j 到 ends）的最优解（dp[j][ends]）。我们用 min 函数来确保我们总是得到最小的值。这里，我们将当前区间分成了两部分：从 j 到 i 和从 i + 1 到 ends，然后加上一些额外的费用或操作（something），这取决于具体问题的需求。

总结：

这个模板的核心思想是通过考虑每个小区间的所有可能性和分割点，逐步构建出更大区间的最优解。就像把一个大拼图分成小块，我们首先把小块拼好，然后再把它们组合成一个完整的图案。通过这种方法，我们能够高效地解决许多复杂的问题。

示例题：石子合并问题（经典区间动态规划）

总是盯着模板看是没有意思的，我们展示示例题目和代码，Show time!

题目描述

有一堆石子分成了 (n) 堆，第 (i) 堆石子的数量是 (a_i)。我们每次可以将相邻的两堆石子合并为一堆，合并的代价是这两堆石子的数量之和。合并之后，这两堆石子就不再分开。问将这 (n) 堆石子合并成一堆的最小代价是多少？

输入格式

• 第一行输入整数 (n)，表示石子的堆数。
• 第二行输入 (n) 个整数 $$a_1,a_2,\dots ,a_n$$，表示每堆石子的数量。

输出格式

• 输出将 (n) 堆石子合并成一堆的最小代价。

示例

输入：

4
1 3 5 2

输出：

22

思考过程

1. 状态定义：

   • 定义 $$dp[j][ends]$$表示将第 (j) 堆石子到第 (ends) 堆石子合并成一堆的最小代价。

2. 转移方程：

   • 我们枚举每个区间 $$[j,ends]$$，并尝试将其分成两部分。对于每个分割点 (i)，计算区间的最优解为：
     $$dp[j][ends]=\min (dp[j][ends],dp[j][i]+dp[i+1][ends]+\text{sum}(j,ends))$$
     其中，$$\text{sum}(j,ends)$$ 表示区间 $$[j,ends]$$ 中所有石子的和，因为我们合并这段区间时，代价是整个区间石子的总和。

3. 初始化：

   • 当区间长度为 1 时，不需要合并，因此 (dp[j][j] = 0)。

4. 计算顺序：

   • 我们先从较短的区间开始计算，然后逐步扩大区间长度。

5. 最终结果：

   • 我们的目标是求出 (dp[1][n])，即将所有石子合并成一堆的最小代价。

使用模板解决问题

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAXN = 310; // 假设最多300堆石子
int dp[MAXN][MAXN];   // dp数组，表示区间最小合并代价
int sum[MAXN];        // 前缀和数组，用于快速计算区间和

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1); // 石子堆，a[1] 到 a[n] 表示石子数量
    
    // 输入石子堆
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i]; // 计算前缀和
    }

    // 初始化dp数组，区间长度为1的代价为0
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }

    // 区间动态规划
    for (int len = 2; len <= n; len++) { // 枚举每个小区间的长度
        for (int j = 1; j + len - 1 <= n; j++) { // 枚举区间的起点
            int ends = j + len - 1; // 区间的终点
            dp[j][ends] = INT_MAX;  // 初始化dp[j][ends]为无穷大

            // 枚举分割点
            for (int i = j; i < ends; i++) {
                dp[j][ends] = min(dp[j][ends], dp[j][i] + dp[i+1][ends] + (sum[ends] - sum[j-1]));
            }
        }
    }

    // 输出将整个区间合并的最小代价
    cout << dp[1][n] << endl;

    return 0;
}

解释

1. 前缀和 sum[]：

   • sum[i] 表示前 (i) 堆石子的和，用于快速计算任意区间 ([j, ends]) 的石子和：
     $$\text{sum}(j,ends)=sum[ends]-sum[j-1]$$
     这样可以在 (O(1)) 时间内计算出区间的和。

2. 主循环：

   • 外层循环遍历不同的区间长度 len，从 2 开始（因为长度为 1 的区间代价为 0），直到长度为 (n)。
   • 中间循环遍历区间的起点 j，并计算区间的终点 ends。
   • 内层循环枚举分割点 i，计算将 ([j, ends]) 分为两个子区间的最小代价，并更新 dp[j][ends]。

总结

通过区间动态规划的模板和应用，我们可以高效地解决“石子合并”这一类区间问题。这个模板的核心思想是通过分割点将问题拆解为子问题，并逐步合并最优解。此方法可以拓展到其他类似的区间合并类问题，例如矩阵连乘、最小代价合并问题等。

总结

区间动态规划是一种高效解决区间问题的算法技术，广泛应用于各类需要处理子区间的竞赛题目中。通过合理划分问题的区间，并利用递归子问题的解构思想，区间DP可以有效降低问题的复杂度。掌握区间DP的状态定义、递推转移和边界处理技巧，可以帮助竞赛选手在面对复杂的区间问题时快速建立模型并找到最优解。

在实际应用中，常见问题如石子合并、括号匹配等都是区间DP的经典应用场景。通过练习这些经典问题，选手可以提升对区间DP的理解和掌握程度。在未来的比赛中，灵活应用区间DP方法，有助于选手高效地解决具有区间特性的复杂问题。