bitworld 的博客
【CSP-算法】区间动态规划
bitworld 最强壮的男人 SU @ 2025-4-26 10:48:09

区间动态规划

区间动态规划（Interval DP）用于解决可分解为子区间的问题，通过合并子区间的解得到整体最优解。其核心步骤包括定义状态、确定转移方程、初始化和按区间长度递推。

一般步骤：

状态定义：dp[i][j] 表示区间 [i, j] 的最优解。
转移方程：枚举分割点 k，合并子区间 [i, k] 和 [k+1, j] 的解。
初始化：处理长度为1的区间。
递推顺序：按区间长度从小到大处理，确保子问题已解。

一、区间DP的核心思想

什么是区间DP？
- 将问题分解为连续子区间，通过合并子区间的最优解得到原问题的最优解。
- 典型特征：问题的解与序列的连续区间相关（如字符串、数组、环形结构）。
适用场景
- 合并类问题（石子合并、能量项链）
- 回文类问题（最长回文子序列、分割回文串）
- 括号匹配类问题（最长有效括号、添加括号的最小代价）
与线性DP的区别
- 状态定义以区间端点 [i][j] 为核心，而非单一位置。

二、区间DP的通用模板

状态定义
- dp[i][j]：表示区间 [i, j] 的最优解（最小值、最大值或可行性）。
状态转移方程
- 枚举分割点 k，合并左右子区间 [i, k] 和 [k+1, j] 的解。
- 通用形式：dp[i][j] = merge(dp[i][k], dp[k+1][j]) + cost(i,j)。
初始化
- 长度为1的区间：dp[i][i] = base_case（如单个元素的代价为0）。
递推顺序
- 按区间长度从小到大遍历（确保计算大区间时子问题已解）。
- 外层循环：for len in 2..n
- 内层循环：枚举起点 i，计算终点 j = i + len - 1。
复杂度分析
- 时间复杂度：通常为 O(n^3)（三重循环）。
- 空间复杂度：O(n^2)（二维数组）。

三、经典问题实战分析

1. 石子合并（合并类问题）

问题描述：合并相邻石子堆，求最小总代价。
关键点：
- 预处理前缀和快速计算区间和。
- 转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i,j)。
代码模板（参考用户提供的代码）。

2. 最长回文子序列（序列类问题）

问题描述：求字符串中最长的回文子序列长度。
关键点：
- 状态转移分情况：首尾字符相等时直接合并，否则选左或右区间。
- 转移方程：dp[i][j] = dp[i+1][j-1] + 2 或 max(dp[i+1][j], dp[i][j-1])。
代码模板（参考用户提供的代码）。

3. 戳气球（环形区间DP问题）

问题描述：环形排列的气球，戳破获得金币，求最大收益。
关键点：
- 环形处理：将数组复制为 2n 长度，转化为线性问题。
- 逆向思维：最后戳破的气球决定左右子问题。
- 转移方程：dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])。

四、常见优化技巧

四边形不等式优化
- 将时间复杂度从 O(n^3) 降低到 O(n^2)，适用于某些单调性条件。
记忆化搜索实现
- 使用递归+记忆化替代递推，简化复杂区间划分的逻辑。
滚动数组压缩空间
- 将空间复杂度从 O(n^2) 降低到 O(n)（某些特殊问题适用）。

五、区间DP的常见陷阱

区间端点定义混乱
- 明确 i 和 j 是闭区间 [i,j] 还是左闭右开 [i,j)。
未处理环形结构
- 环形问题需破环成链（如复制数组到 2n 长度）。
错误的遍历顺序
- 必须先处理小区间，再处理大区间。

六、练习题推荐

P1880 [NOI1995] 石子合并（洛谷）

题目描述

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

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

输入格式

数据的第 $1$ 行是正整数 $N$ ，表示有 $N$ 堆石子。

第 $2$ 行有 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆石子的个数。

输出格式

输出共 $2$ 行，第 $1$ 行为最小得分，第 $2$ 行为最大得分。

输入输出样例 #1

输入 #1

4
4 5 9 4

输出 #1

43
54

说明/提示

$1\leq N\leq 100$ ， $0\leq a_i\leq 20$ 。

参考代码

#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N];  // 前缀和
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i], s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++ )//区间长度
        for (int i = 1; i + len - 1 <= n; i ++ )//左端点
        {
            int j = i + len - 1;//右端点
            f[i][j] = 1e8;
            for (int k = i; k < j; k ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }

    cout << f[1][n] << endl;

    return 0;
}

LeetCode 312. 戳气球

题目描述
给定 n 个气球，编号 0 到 n-1，每个气球上标有数字 nums[i]。戳破气球 i 可获得 nums[left] * nums[i] * nums[right] 个硬币（left 和 right 是 i 的相邻气球序号）。求戳破所有气球能获得的最大硬币数量。

动态规划核心思路

状态定义：dp[i][j] 表示开区间 (i, j) 内戳破所有气球的最大收益（不戳破 i 和 j 处的气球）。
状态转移：枚举区间内最后一个戳破的气球 k，则 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])。
初始化：在数组首尾添加虚拟气球 1，形成新数组 newnums，确保边界条件。
遍历顺序：按区间长度从小到大递推，i 从下往上，j 从左往右。

C++代码

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

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    vector<int> newnums(n + 2, 1); // 首尾添加1
    for (int i = 1; i <= n; ++i) newnums[i] = nums[i - 1];
    
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int i = n + 1; i >= 0; --i) { // i从大到小
        for (int j = i + 1; j < n + 2; ++j) { // j从小到大
            for (int k = i + 1; k < j; ++k) { // 枚举最后戳破的k
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + newnums[i] * newnums[k] * newnums[j]);
            }
        }
    }
    return dp[0][n + 1];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];
    cout << maxCoins(nums) << endl;
    return 0;
}

LeetCode 516. 最长回文子序列

题目描述
给定字符串 s，找出其最长回文子序列的长度（子序列不要求连续）。

动态规划核心思路

状态定义：dp[i][j] 表示子串 s[i..j] 的最长回文子序列长度。
状态转移：
- 若 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2；
- 否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
初始化：单个字符的回文长度为1，即 dp[i][i] = 1。
遍历顺序：i 从后往前遍历，j 从 i+1 开始往后遍历。

C++代码

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

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; ++j) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    string s;
    cin >> s;
    cout << longestPalindromeSubseq(s) << endl;
    return 0;
}

关键总结

戳气球：
- 逆向思维，通过最后戳破的气球 k 分割子问题。
- 需在数组首尾添加虚拟气球避免边界问题。
最长回文子序列：
- 利用回文的对称性，分情况处理首尾字符。
- 遍历顺序需确保子问题已解（i 逆序，j 顺序）。

LeetCode 1039. 多边形三角剖分的最低得分

题目描述

给定一个凸 N 边形，顶点按顺时针顺序标记为 A[0], A[1], ..., A[N-1]。将多边形剖分为 N-2 个三角形，每个三角形的值为顶点乘积，总分为所有三角形值之和。要求找到总分的最小值。

示例
输入：[3,7,4,5]
输出：144
解释：两种剖分方式得分分别为 245 和 144，取最小值。

动态规划思路

状态定义
dp[i][j] 表示顶点 i 到 j 组成的子多边形的最小得分（闭区间 [i, j]）。
状态转移
枚举区间 [i, j] 内的分割点 k（i < k < j），将多边形分为三部分：
- 三角形 (i, k, j)
- 子多边形 [i, k]
- 子多边形 [k, j]
  转移方程：
```
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k])  
```
初始化与遍历顺序
- 初始化 dp[i][i+1] = 0（相邻顶点无法构成三角形）
- 按区间长度从小到大递推，确保子问题已计算。

C++代码

  #include <iostream>
  #include <vector>
  #include <climits>
  using namespace std;
  
  int minScoreTriangulation(vector<int>& A) {
      int n = A.size();
      vector<vector<int>> dp(n, vector<int>(n, 0));
      for (int i = n - 3; i >= 0; --i) { // 倒序枚举i
          for (int j = i + 2; j < n; ++j) { // j从i+2开始（至少3个顶点）
              dp[i][j] = INT_MAX;
              for (int k = i + 1; k < j; ++k) { // 枚举分割点k
                  dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]);
              }
          }
      }
      return dp[0][n - 1];
  }
  
  int main() {
      int n;
      cin >> n;
      vector<int> A(n);
      for (int i = 0; i < n; ++i) cin >> A[i];
      cout << minScoreTriangulation(A) << endl;
      return 0;
  }

LeetCode 1547. 切棍子的最小成本

题目描述

给定长度为 n 的木棍和切割点数组 cuts，每次切割成本为当前木棍长度。求按最优顺序切割后的最小总成本。

示例
输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：最优切割顺序为 [3,5,1,4]，总成本 7+4+3+2=16。

动态规划思路

状态定义
dp[i][j] 表示处理切割点 cuts[i] 到 cuts[j] 之间的木棍段的最小成本（闭区间 [i, j]）。
状态转移
枚举区间 [i, j] 内的切割点 k，将木棍分为 [i, k] 和 [k, j] 两部分：
```
dp[i][j] = min(dp[i][k] + dp[k][j]) + (cuts[j] - cuts[i])  
```
预处理与遍历顺序
- 将 cuts 排序并添加端点 0 和 n，形成新数组 cuts_ext。
- 按区间长度从小到大递推，外层倒序枚举 i，内层正序枚举 j。

C++代码

  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <climits>
  using namespace std;
  
  int minCost(int n, vector<int>& cuts) {
      cuts.push_back(0);
      cuts.push_back(n);
      sort(cuts.begin(), cuts.end());
      int m = cuts.size();
      vector<vector<int>> dp(m, vector<int>(m, 0));
      
      for (int i = m - 2; i >= 0; --i) { // 倒序i
          for (int j = i + 2; j < m; ++j) { // j从i+2开始（至少两个切割点）
              dp[i][j] = INT_MAX;
              for (int k = i + 1; k < j; ++k) { // 枚举切割点k
                  dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
              }
              dp[i][j] += cuts[j] - cuts[i];
          }
      }
      return dp[0][m - 1];
  }
  
  int main() {
      int n, m;
      cin >> n >> m;
      vector<int> cuts(m);
      for (int i = 0; i < m; ++i) cin >> cuts[i];
      cout << minCost(n, cuts) << endl;
      return 0;
  }

区间动态规划的核心在于分治与合并：它通过定义状态 dp[i][j] 来表示序列（或环形结构）中区间 [i, j] 的最优解，并按照区间长度从小到大的顺序进行递推。通过枚举分割点 k，将大区间问题分解为 [i, k] 和 [k+1, j] 等子区间问题，合并子问题的最优解并加上可能的合并代价，最终得到原区间的解。熟练掌握这种自底向上的构建方式，注意正确的遍历顺序、细致的边界初始化以及对环形结构的特殊处理（如“破环成链”），是运用区间DP解决石子合并、最长回文、括号匹配、多边形剖分等一类问题的关键所在，其基础时间复杂度通常为 O(n³)。

【CSP-算法】区间动态规划

区间动态规划

一般步骤：

一、区间DP的核心思想

二、区间DP的通用模板

三、经典问题实战分析

1. 石子合并（合并类问题）

2. 最长回文子序列（序列类问题）

3. 戳气球（环形区间DP问题）

四、常见优化技巧

五、区间DP的常见陷阱

六、练习题推荐

P1880 [NOI1995] 石子合并（洛谷）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

参考代码

LeetCode 312. 戳气球

LeetCode 516. 最长回文子序列

关键总结

LeetCode 1039. 多边形三角剖分的最低得分

题目描述

动态规划思路

C++代码

LeetCode 1547. 切棍子的最小成本

题目描述

动态规划思路

C++代码

还没有账户？

登录