【算法总结】区间动态规划（区间DP）详解

一、 什么是区间DP？

• 定义：在一段区间上进行动态规划，求解这段区间上的最优解。
• 核心思想：将一个大区间的问题分解成两个或多个小区间的问题，通过合并小区间的最优解来得到大区间的最优解。这完美地体现了分治和最优子结构的思想。
• 目标：最终通常是求解整个序列区间 [1, n] 的最优值。

二、 为什么使用区间DP？

1. 问题对象是一个线性序列（如字符串、数组）或一个环（通常通过“破环成链”技巧处理）。
2. 问题的解与序列中连续的一段（即区间）有关。
3. 问题满足最优子结构：大区间的最优解依赖于其包含的小区间的最优解。
4. 问题满足无后效性：当前状态的值一旦确定，就不会再受后续决策的影响。

• 环形数组的最大子数组和
• 环形队列的模拟
• 环形动态规划问题

三、 状态设计与经典思路

1. 基本状态设计

• 最大/最小价值
• 最大/最小分数
• 构成特定结构的方案数
• true/false（表示区间能否达成某种状态）

2. 状态转移方程

// 1. 初始化长度为1的区间
for (int i=1;i<=n;i++)
{
    dp[i][i]=...; // 初始条件
}

// 2. 第一层循环：枚举区间长度 len (从 2 到 n)
for(int len=2;len<=n;len++)
{
    // 3. 第二层循环：枚举区间起点 i (终点 j=i+len-1)
    for(int i=1;i+len-1<=n;i++)
	{
        int j=i+len-1;
        // 4. 第三层循环：枚举分割点 k (在 [i,j] 之间)
        for(int k=i;k<j;k++)
		{
            // 状态转移：dp[i][j] 由 dp[i][k] 和 dp[k+1][j] 合并而来
            dp[i][j]=...;
        }
    }
}

3. 经典转移模型

1. 枚举分割点合并：dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+cost(i,j,k))
   • 适用场景：石子合并、多边形剖分等。
   • 理解：将 [i,j] 分成 [i,k] 和 [k+1,j]，先解决两个子问题，再将它们合并，合并会产生代价或收益 cost。
2. 根据区间端点性质转移：`dp[i][j]=max{dp[i+1][j],dp[i][j-1],dp[i+1][j-1],...};
   • 适用场景：括号匹配、回文子序列等。
   • 理解：根据区间两端的字符或元素是否匹配、是否同时选取来进行状态转移。

四、 经典例题分析

例题： 【NOI1995】 石子合并 (Luogu P1880)

• 环的处理：经典“破环成链”技巧。将长度为 n 的环复制一遍，变成长度为 2n 的链。然后在这个链上做区间DP，最后答案就是所有长度为 n 的区间 [i, i+n-1] (1 <= i <= n) 中的最优值。
• 状态设计：dp_min[i][j] 表示合并区间 [i, j] 的石子所需的最小代价。
• 状态转移：枚举最后一次合并的分割点 k。合并 [i, j] 的代价 = 合并 [i, k] 的代价 + 合并 [k+1, j] 的代价 + 区间 [i, j] 的总石子数（本次合并的代价）。 dp_min[i][j] = min(dp_min[i][k] + dp_min[k+1][j] + sum(i, j))
• 前缀和优化：为了快速计算 sum(i, j)，可以预处理前缀和数组 s，使得 sum(i, j) = s[j] - s[i-1]。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum[505],dp[505][505],n,a[505];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=n+1;i<=n+n;i++)
	{
		a[i]=a[i-n];
		sum[i]=sum[i-1]+a[i];
	}
	memset(dp,0x3f,sizeof dp);
	for(int i=1;i<=2*n;i++)
		dp[i][i]=0;
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n*2;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
		}
	}
	int mini=1e9;
	for(int i=1;i<=2*n;i++)
	{
		if(dp[i][i+n-1]==0)
			continue;
		mini=min(mini,dp[i][i+n-1]);
	}
	cout<<mini<<endl;
	memset(dp,0,sizeof dp);
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n*2;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)
				dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
		}
	}
	mini=-1e9;
	for(int i=1;i<=2*n;i++)
	{
		mini=max(mini,dp[i][i+n-1]);
	}
	cout<<mini;
	return 0;
}

五、 常见技巧与注意事项

1. 破环成链：对于环形问题，将原序列复制一份接在后面，形成长度为 2n 的链。DP完成后，在所有长度为 n 的区间中寻找答案。
2. 前缀和/差分：当状态转移涉及区间和时，使用前缀和可以快速计算，将O(n)的求和优化到O(1)。
3. 初始化：务必正确初始化长度为1和长度为2的区间，这是状态转移的基础。
4. 循环顺序：务必牢记 长度 -> 起点 -> 分割点 的循环顺序，这是区间DP正确性的保证。
5. 时间复杂度：三重循环导致时间复杂度通常为 O(n³)，因此 n 的规模一般在 100 ~ 500 左右。如果 n 达到 1000，可能需要四边形不等式等优化。

六、 习题推荐（按难度排序）

1. 入门
   • Luogu P1430 序列取数：基础的区间DP，理解“双方都最优操作”的含义。
   • Luogu P1063 [NOIP2006 提高组] 能量项链：经典的环状区间DP，与石子合并类似。
2. 巩固
   • Luogu P3146 [USACO16OPEN] 248 G：状态定义需要一些转化，思考如何表示“合并成一个数”。
   • Luogu P3205 [HNOI2010] 合唱队：状态设计需要增加一维，表示最后一次加入的人是在左边还是右边 (dp[i][j][0/1])。
3. 提高
   • Luogu P4170 [CQOI2007] 涂色：思考如何用最少的次数覆盖一个区间。
   • Luogu P4302 [SCOI2003] 字符串折叠：区间DP与字符串处理结合，需要判断循环节。
   • Luogu P1220 关路灯：经典的区间DP拓展，状态中需要记录老张的位置 (dp[i][j][0/1])。