浅谈区间 DP

区间 DP 不是一种有固定题意和转移的具体模型。

它更像是一种组织子问题的方式：当操作过程中某个中间对象始终对应原序列的某一段连续区间，并且在固定一个关键决策后，大区间能够被拆成严格更小的区间时，可以尝试区间状态。

本文从具体问题出发，观察区间状态怎样产生，以及问题条件变化后，状态与转移会怎样变化。

一、区间合并 & 区间状态

P1880 石子合并：从相邻合并中产生区间状态

问题

P1880 石子合并
有 $N$ 堆环形排列的石子，每次只能合并相邻两堆，合并代价为两堆石子的总重量。求最终合并成一堆的最小代价与最大代价。
数据规模：$N \le 100$。

先忽略环形，只考虑线性序列。

对于一个序列问题，先考虑线性状态定义：$f_{i}$ 表示把前 $i$ 堆石子合并为一堆的最小代价。

假设最后一次是把 $[1, k]$ 堆和 $[k+1, i]$ 堆合并，那么左边可以由 $f_k$ 表示，右边这个区间不是前缀，原状态无法表示。

问题不在于我们没找到正确的转移，而是状态的定义没有封闭，无法匹配转移。

由于每次只能合并相邻石堆，所以无论按照什么顺序合并，任意中间石堆都一定来自原序列中的一段连续区间。因此不妨定义：$f_{l,r}$ 表示把区间 $[l, r]$ 合并为一堆的最小代价。

考虑最后一次合并，区间 $[l, r]$ 是由某个分割点 $k$ 形成的两堆 $[l, k]$ 和 $[k+1, r]$ 合并而成。

于是我们可以得到转移：$\displaystyle f_{l,r} = \min_{l \le k < r}\left( f_{l,k} + f_{k+1, r} + \sum_{i=l}^{r} a_i \right)$。

这里的 $k$ 是在枚举完整方案的最后一次合并位置。任意合法方案都有这样一个 $k$，固定 $k$ 后，左右两侧又能分别独立求最优值。

由于 $f_{l,r}$ 只依赖于严格更小的区间，所以我们从小区间到大区间递推。

若要维护最大代价，把 $\min$ 改成 $\max$ 即可，区间和用 [[前缀和]] 优化。

▶

P1880

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        a[i + n] = a[i];
    }

    int N = n << 1;
    for( int i = 1; i <= N; ++ i ) {
        sum[i] = sum[i-1] + a[i];
        minf[i][i] = maxf[i][i] = 0;
    }

    for( int len = 2; len <= n; ++ len ) {
        for( int l = 1; l + len - 1 <= N; ++ l ) {
            int r = l + len - 1;
            minf[l][r] = inf;
            maxf[l][r] = -inf;

            ll cur = sum[r] - sum[l-1];
            for( int k = l; k < r; ++ k ) {
                minf[l][r] = min( minf[l][r], minf[l][k] + minf[k+1][r] + cur );
                maxf[l][r] = max( maxf[l][r], maxf[l][k] + maxf[k+1][r] + cur );
            }
        }
    }

    ll minans = inf, maxans = -inf;
    for( int i = 1; i <= n; ++ i ) {
        minans = min( minans, minf[i][i+n-1] );
        maxans = max( maxans, maxf[i][i+n-1] );
    }
    cout << minans << '\n' << maxans << '\n';
}

环形处理

一般来说，处理环形序列的通用手段，就是复制一份原数组，任意长度 $N$ 的线性区间都对应环上的一种断开方式，最后枚举 $[i, i+N-1]$ 即可。

从这题，我们可以得到区间 DP 最基础的产生过程：

前缀状态的局限性 $\to$ 中间对象对应区间 $\to$ 左右端点定义状态 $\to$ 枚举最后一次操作

但石子合并还有一个性质，区间和是可以直接从原数组中算出来的，所以不需要额外状态记录。

那么，如果合并后的对象不是由区间和描述，而是由边界决定呢？

P1063 能量项链：区间合并时需要哪些信息

问题

P1063 能量项链
每颗珠子可以表示为一对首尾标记，相邻珠子能够合并，并产生由边界决定的能量。求合并完整条环形项链能够得到的最大能量。
数据规模：$N \le 100$。

这道题看起来仍然是“不断合并相邻对象”，所以我们沿用上一题的区间结构。

设第 $i$ 颗珠子表示为 $(a_{i}, a_{i+1})$，定义 $f_{l,r}$ 表示合并 $[l, r]$ 能得到的最大能量。

若最后一次合并发生在 $k$ 与 $k+1$ 之间，则 $\displaystyle f_{l,r} = \max_{l \le k < r}(f_{l, k} + f_{k+1, r} + a_{l} \cdot a_{k+1} \cdot a_{r+1} )$。

这题和石子合并有相同的区间拆分：$[l,r] \to [l,k] + [k+1, r]$。

但合并的代价不同，这就说明了，区间以后要怎样与其他区间结合，决定了转移要保留哪些信息。

区间 $[l, r]$ 只描述子问题的范围，而状态还要不要增加信息，取决于状态转移是否需要新的信息。

上面两题都是通过最后一次合并拆成两部分，很容易给人一种错觉：区间 DP 就是枚举分割点。

• 类似题目：P4302 字符串折叠

但如果一次操作只处理区间端点，还需要枚举分割点吗？

二、区间 DP 不一定枚举分割点

P2890 Cheapest Palindrome：端点缩区间

问题

P2890 Cheapest Palindrome G
给定一个长度为 $m$ 的字符串，可以增加或删除字符。每种字符的增加、删除代价不同，求把字符串变成回文串的最小代价。
数据规模：$m \le 2e3$。

这道题的每次决策都围绕当前子串的左右端点展开。处理一个端点后，剩余部分仍然是连续子串，因此考虑区间状态。

定义 $f_{l,r}$ 表示把子串 $s[l \dots r]$ 变成回文串的最小代价。

接着考虑转移，若 $s_l=s_r$，两端可以直接匹配回文：$f_{l,r} = f_{l+1,r-1}$。

若 $s_l\ne s_r$，我们可以处理左端点，也可以处理右端点。我们以 $s_{l}$ 左端点为例，为了形成回文串，我们可以进行两种操作：删除 $s_{l}$，或者在右侧增加一个 $s_{l}$。

这两个操作看起来完全不同，但是它们对原字符串的效果是相同的，都让问题进入了 $[l+1,r]$ 这个子串。

于是我们只需要令 $cost(c) = \min(add_{c}, del_{c})$，转移很自然就能得到：$f_{l,r} = \min( f_{l+1,r}+cost(s_l), f_{l,r-1}+cost(s_r) )$。

这里没有分割点，单状态只有常数个转移，总复杂度为 $O(N^2)$。

值得一提的是，这题的初始化状态需要处理空串 —— 即左端点大于右端点的状态。举个例子 aa 长度为 2，f[1][2] = min( f[1][2], f[2][1] )，那么 f[2][1] 是什么呢？

▶

P2890

int cost[30];
ll f[maxn][maxn];

void solve( ) {
    int n = read( ), m = read( );
    string s;
    cin >> s;
    s = " " + s;
    for( int i = 1; i <= n; ++ i ) {
        char ch; int a, b;
        cin >> ch >> a >> b;
        cost[ch - 'a'] = min(a, b);
    }
    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            f[i][j] = inf;
        }
    }
    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= i; ++ j ) {
            f[i][j] = 0;
        }
    }
    for( int len = 2; len <= m; ++ len ) {
        for( int l = 1; l + len - 1 <= m; ++ l ) {
            int r = l + len - 1;
            if( s[l] == s[r] ) f[l][r] = min( f[l][r], f[l+1][r-1] );
            f[l][r] = min( f[l][r], f[l+1][r] + cost[s[l] - 'a'] );
            f[l][r] = min( f[l][r], f[l][r-1] + cost[s[r] - 'a'] );
        }
    }
    cout << f[1][m] << '\n';
}

这题可以得到的新理解是：区间 DP 的关键在于一次决策以后，可以将尚未解决的部分表示为更小的区间。

不过，看到字符串两端相同以后直接缩区间，也很容易形成另一个模板。

• 类似题目：P1005 矩阵取数游戏 | P4302 字符串折叠

下一题恰好说明：同样是观察端点，相同字符的作用也未必相同。

P4170 涂色：合并端点操作

问题

P4170 涂色
每次可以把一段连续区间涂成同一种颜色，求得到目标颜色序列的最少操作次数。
数据规模：$N \le 50$。

这题有点类似刚才的回文字符串，我们尝试定义区间状态：$f_{l,r}$ 表示完成区间 $[l,r]$ 的最少涂色次数。

接着考虑转移，如果 $s_{l} \neq s_{r}$，那么朴素的方法是把区间拆成两段分别完成： $\displaystyle f_{l,r} =\min_{l \le k < r}(f_{l,k} + f_{k+1,r})$。

如果 $s_{l} = s_{r}$，因为涂某一个端点的时候，可以顺带覆盖另一端，于是：$f_{l,r} = \min(f_{l+1,r}, f_{l, r-1})$。

▶

P4170

ll f[maxn][maxn];

void solve( ) {
    string s;
    cin >> s;
    int n = s.length( );
    s = " " + s;

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            f[i][j] = inf;
        }
    } 
    for( int i = 1; i <= n; ++ i ) {
        f[i][i] = 1;
    }

    for( int len = 2; len <= n; ++ len ) {
        for( int l = 1; l + len - 1 <= n; ++ l ) {
            int r = l + len - 1;
            if( s[l] == s[r] ) {
                f[l][r] = min( f[l+1][r], f[l][r-1] );
            } else {
                for( int k = l; k < r; ++ k ) {
                    f[l][r] = min( f[l][r], f[l][k] + f[k+1][r] );
                }
            }
        }
    }
    cout << f[1][n] << '\n';
}

对比 P2890 和 P4170，我们能发现，端点在不同的题设中的含义也不同。

所以不能直接把 “端点相同” 记忆成转移公式，而需要追问：端点关系究竟怎样改变了原问题的操作过程。

到目前为止，我们的转移方向都是很明确的，是否存在一些很奇怪的区间转移呢？

P3205 合唱队：逆向过程中的端点扩张

问题

P3205 合唱队
每个人进入队伍时，只能站在当前队伍的最左侧或最右侧，如果比上一个高去右边，比上一个矮去左边。给出最终身高序列，求有多少种合法进场顺序。
数据规模：$N \le 1000$。

第一个人可以是最终序列中的任意位置，之后队伍不断向左右扩张，所以如果我们定义：已经进入了多少人，还需要记录当前队伍占据了哪些位置。

由于这题已经给出了最终的序列，我们可以尝试反过来构造。最后一个人一定在队伍的左端或者右端，删掉最后一个人后，剩余的人恰好对应最终序列中的某一段连续的区间。

于是可以尝试区间状态定义：$f_{l,r}$ 表示形成区间 $[l,r]$ 的方案数。

但是这样没法转移，因为我们不确定上一个最后进入的人是谁，朴素的想法就是增加一个状态记录这个信息。

于是我们得到第二版定义：$f_{l,r,0/1}$，其中 $f_{l,r,0}$ 表示最后入队的位置在左边，$f_{l,r,1}$ 表示最后入队的位置在右边。

以最后进入左端点为例，此前可能的状态是：$f_{l+1,r,0}$ 或 $f_{l+1,r,1}$，最后根据身高关系约束转移即可。

这题还要注意初始化。长度为 $1$ 时，“最后从左端进入” 和 “最后从右端进入” 实际表示同一个方案。若两个状态都初始化为 $1$，所有方案都会被重复计算，因此只需要初始化其中一种。

▶

P3205

ll dp[maxn][maxn][2];
int a[maxn];

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );

    // for( int i = 1; i <= n; ++ i ) dp[i][i][0] = dp[i][i][1] = 1;
    for( int i = 1; i <= n; ++ i ) dp[i][i][0] = 1;
    
    for( int len = 2; len <= n; ++ len ) {
        for( int l = 1; l + len - 1 <= n; ++ l ) {
            int r = l + len - 1;
            if( a[l] < a[l+1] ) dp[l][r][0] += dp[l+1][r][0];
            if( a[l] < a[r] ) dp[l][r][0] += dp[l+1][r][1];

            if( a[r] > a[r-1] ) dp[l][r][1] += dp[l][r-1][1];
            if( a[r] > a[l] ) dp[l][r][1] += dp[l][r-1][0];

            dp[l][r][0] %= mod;
            dp[l][r][1] %= mod;
        }
    }
    cout << ( dp[1][n][0] + dp[1][n][1] ) % mod << '\n';
}

由此我们发现，区间 DP 并不保证 $f_{l,r}$ 这个状态是足够的，我们需要保存 “决定未来的最小信息”，就如这题的 0/1 这一维度。

但区间 DP 中的 “最后一步” 有没有可能发生在区间内部呢？比如说下面这一题。

P5851 Greedy Pie Eaters：最后处理的支点

问题

P5851 Greedy Pie Eaters P
有 $M$ 头奶牛和 $N$ 个派。第 $i$ 头奶牛有活动区间 $[l_i,r_i]$ 和权值 $w_i$。轮到一头奶牛时，它会吃掉活动区间内所有尚未被吃掉的派；被选中的奶牛必须至少吃到一个派。求能够获得的最大权值和。
数据规模：$N,M \le 300$。

这题我的第一思路是 贪心，比如按照牛能吃到的派的权值排序呢？可是这样会遇到一个问题，因为一头牛会把这整个区间的派都吃了，所以状态里就必须记录哪些饼还在，可……这样的状态规模就变成 $2^{N}$，这就需要我们寻找优化思路了。

正着推不行，那倒着推呢，考虑一下最后一步是什么？假设在区间 $[l, r]$ 中，位置 $k$ 最后被某头奶牛选择。此时，在处理 $k$ 这一点之前，$k$ 左侧和右侧的选择已经全部完成，由于 $k$ 仍然存在，所以原问题就可以化为两个独立的连续子问题 $[l, k - 1]$，以及 $[k+1, r]$。

不妨定义 $f_{l,r}$ 表示只考虑区间 $[l, r]$ 时能够得到的最大权值。

最后一头奶牛必须满足：活动区间完全包含于 $[l,r]$，并且覆盖位置 $k$。因此再定义： $g_{l,r,k}$ 表示活动区间包含于 $[l, r]$ 且覆盖位置 $k$ 的奶牛的最大权值。

枚举最后被处理的位置 $k$，得到转移：$\displaystyle f_{l,r} = \max_{l \le k \le r}(f_{l,k-1} + f_{k+1,r} + g_{l,r,k})$。

这里的 $k$ 和第一题的分割点不同，石子合并中的 $k$ 表示最后合并的两个区间之间的边界，而在这道题中 $k$ 是最后被处理的节点，因为它最后被处理，所以才分割，二者的因果是反过来的。

如果随意选择一个位置划分，而不把它放进最后一步，后续仍可能存在跨越该位置的奶牛，左右两侧也就无法独立求解。

剩下的问题就是预处理 $g_{l,r,k}$ 了，在固定 $k$ 后，随着区间 $[l,r]$ 的扩大，可选奶牛只会增加，因此可以用类似区间 DP 的状态扩展：$g_{l,r,k} = \max(g_{l+1,r,k}, g_{l,r-1,k}, w_{l,r,k})$。

$w_{l,r,k}$ 表示活动区域刚好为 $[l,r]$ 且覆盖 $k$ 的奶牛的最大权值。

▶

P5851

ll f[maxn][maxn];
ll g[maxn][maxn][maxn];

void solve( ) {
    int n = read( ), m = read( );

    for( int i = 1; i <= m; ++ i ) {
        int w = read( ), l = read( ), r = read( );
        for( int k = l; k <= r; ++ k ) {
            g[l][r][k] = max( g[l][r][k], w );
        }
    }

    for( int len = 1; len <= n; ++ len ) {
        for( int l = 1; l + len - 1 <= n; ++ l ) {
            int r = l + len - 1;
            for( int k = l; k <= r; ++ k ) {
                if( l < k ) g[l][r][k] = max( g[l][r][k], g[l+1][r][k] );
                if( k < r ) g[l][r][k] = max( g[l][r][k], g[l][r-1][k] );
            }
        }
    }

    for( int len = 1; len <= n; ++ len ) {
        for( int l = 1; l + len - 1 <= n; ++ l ) {
            int r = l + len - 1;
            for( int k = l; k <= r; ++ k ) {
                f[l][r] = max( f[l][r], f[l][k-1] + f[k+1][r] + g[l][r][k] );
            }
        }
    }

    cout << f[1][n] << '\n';
}

综上我们发现，区间 DP 需要的大概率不是一个普通的分割点，而是一个关键事件 —— 固定这个事件最后发生以后，原来的问题会分裂成若干个独立的子区间问题。

所以我们发现，前面几题的转移形式虽然不同，但本质都是在找一个能让区间变小且独立的最后操作。

三、总结

区间 DP 的核心不是二维数组，也不是枚举分割点，而是找到一个能够使区间独立的关键决策，使分裂后的若干子问题更小，直至可以直接处理，以及少量边界信息。

如果在状态定义的过程中卡住，不妨从下面几个问题入手：

1. 原来的状态为什么无法封闭？
2. 中间对象是否始终连续？
3. 固定哪个关键操作后，大问题能够拆成更小区间？
4. 拆出的子问题是独立的吗？
5. 区间向未来组合时还需要记录什么信息？
6. 这些信息能否由端点和原数组恢复？
7. 状态数量与单状态转移代价是否能够接受？

最后，区间状态通常由 $\mathcal{O}(N^{2})$ 个，但总复杂度取决于单状态的决策数量，所以，区间 DP 的复杂度可能是 $\mathcal{O}(N^{2})$，也可能是 $\mathcal{O}(N^{3})$，也可能是 $\mathcal{O}(NV)$。

若再利用值域、单调性或其他特殊性质重新编码状态，复杂度还可能进一步变化。 #todo