区间dp总结

lyxqqq1 · 2025-10-18 14:03:43 · 个人记录

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

一、什么是区间DP？

区间DP是动态规划的一个分支，它的定义域和状态通常与一个序列上的区间有关。

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

二、为什么使用区间DP？

当你发现一个问题具有以下特征时，可以考虑使用区间DP：

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

注 破环成链是一种处理环形数据结构（如环形数组、环形队列）的常用技巧。

核心思想：
将环形结构复制一份并接在原数组的末尾，从而将环形问题转化为线性问题处理。

举例：
假设有一个环形数组 [A, B, C, D]，复制一份得到：
[A, B, C, D, A, B, C, D]
这样，环上任意长度为 n 的连续段，都可以在这个长度为 2n 的线性数组中找到。

应用场景：

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

优点：简化问题，避免复杂的取模计算；缺点：空间占用翻倍。

三、状态设计与经典思路

1. 基本状态设计

最经典的状态设计是： dp[i][j] 表示区间 [i,j] 上的最优解（或某种状态）。

这个“最优解”根据题目不同，可能是：

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

2. 状态转移方程

区间DP的状态转移通常遵循一个固定的模式：枚举区间长度和起点，再枚举分割点。

// 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]=...;
        }
    }
}

为什么按长度枚举？ 因为计算大区间 [i,j] 时，其所有小区间 [i,k] 和 [k+1,j] 的长度都必须小于 j-i+1。按长度从小到大的顺序枚举，可以保证在计算大区间时，它依赖的所有小区间都已经被计算过了。

3. 经典转移模型

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

四、经典例题分析

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

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

分析：

环的处理：经典“破环成链”技巧。将长度为 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;
}

五、常见技巧与注意事项

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

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

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

总结： 区间DP的精髓在于“分治”和“合并”。掌握其通用的循环框架和状态设计思想，再通过大量练习积累不同题型的转移技巧，你就能在面对相关问题时游刃有余。

区间dp总结

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

一、 什么是区间DP？

二、 为什么使用区间DP？

三、 状态设计与经典思路