《区间dp》

区间动态规划（Interval DP）概述

区间动态规划是一种用于解决涉及区间最优解的动态规划方法，通常适用于需要枚举或合并子区间的问题。其核心思想是将问题分解为更小的区间，通过状态转移方程合并子区间的结果。

区间DP的常见应用场景

• 矩阵链乘法（最优计算顺序）
• 石子合并问题（最小/最大合并代价）
• 括号匹配问题（最长有效括号子序列）
• 分割回文串（最少分割次数）

区间DP的基本模板（C++实现）

区间DP通常采用二维数组dp[i][j]表示区间[i, j]的最优解，并通过三重循环实现：外层枚举区间长度，中层枚举起点，内层枚举分割点。

int dp[N][N]; // dp[i][j]表示区间[i,j]的最优解
memset(dp, 0, sizeof(dp)); // 初始化for (int len = 2; len <= n; len++) {       // 枚举区间长度for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点iint j = i + len - 1;                // 终点jdp[i][j] = INF; // 初始化为极大值（求最小值时）for (int k = i; k < j; k++) {       // 枚举分割点kdp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, j));}}
}

关键点与优化

1. 初始化：

   • 单个区间（len=1）的值通常直接初始化（如dp[i][i] = 0）。
   • 根据问题需求，可能需要预处理前缀和或其他辅助数组。

2. 状态转移方程：

   • 根据问题类型设计合并逻辑。例如：
     • 石子合并：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])
     • 最长回文子序列：dp[i][j] = dp[i+1][j-1] + 2（当s[i] == s[j]时）

3. 常见优化：

   • 四边形不等式：适用于某些单调性优化的场景，可将时间复杂度从$O(n^3)$降至$O(n^2)$。
   • 记忆化搜索：递归实现可能更直观，但需注意重复计算问题。

示例：石子合并问题

问题描述：合并相邻石子堆，每次合并代价为两堆石子总数，求最小总代价。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 310;
int n, s[N], dp[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;dp[i][j] = 1e9;for (int k = i; k < j; k++) {dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);}}}cout << dp[1][n] << endl;return 0;
}

注意事项

• 边界处理：确保区间端点i和j的合法性。
• 方向性：部分问题需区分方向（如回文问题需从中心扩展）。
• 空间优化：对于大规模数据，可考虑滚动数组或其他压缩方法。