区间动态规划 (Interval DP)¶

区间动态规划是以“区间长度”作为阶段推进的动态规划分支。其核心特征是：大区间的解是由若干相互独立、无交集、可拼接的较小子区间的解合并优化而来。

1. 区间 DP 经典范式与循环顺序¶

1.1 核心状态模型¶

定义 $dp[i][j]$ 表示将闭区间 $[i, j]$ 内的元素合并或消除所能达到的最优值（最小代价或最大收益）：

\[ dp[i][j] = \min_{i \le k < j} \Big( dp[i][k] + dp[k + 1][j] \Big) + \text{cost}(i, j) \]

1.2 循环顺序铁律 (Loop Invariant)¶

在区间 DP 中，若使用朴素的 $i$ 从 $0$ 到 $N$ 递增、$j$ 从 $i$ 到 $N$ 递增的两重循环，在计算 $dp[i][j]$ 时，所需的较长子区间（例如右半边 $dp[k+1][j]$）可能尚未被计算出来，导致状态转移无后效性被破坏。

标准循环范式：
第一层循环：枚举区间长度 $len$（从 $2$ 到 $N$）；
第二层循环：枚举区间左端点 $i$（$0 \le i \le N - len$），右端点自动确定为 $j = i + len - 1$；
第三层循环：枚举区间分割决策点 $k \in [i, j - 1]$。

#include <vector>
#include <algorithm>

const int INF = 1e9;

// 经典区间合并模板 (如石子合并)
int interval_dp_template(int n, const std::vector<int>& cost) {
    // dp[i][j] 表示合并区间 [i, j] 的最小代价
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

    // 1. 枚举区间长度 len (从 2 到 n)
    for (int len = 2; len <= n; ++len) {
        // 2. 枚举左端点 i
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1; // 右端点
            dp[i][j] = INF;
            // 3. 枚举分割点 k
            for (int k = i; k < j; ++k) {
                dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost[j] - (i > 0 ? cost[i - 1] : 0));
            }
        }
    }
    return dp[0][n - 1];
}

时间复杂度：$\mathcal{O}(N^3)$
空间复杂度：$\mathcal{O}(N^2)$

2. 破环成链技巧 (Circular Interval DP)¶

在许多竞赛题目中，石子或节点排列在环形结构上（首尾相连），任意位置均可作为断开点。

展开技巧：倍长数组¶

将长度为 $N$ 的环复制一倍，拼接成长度为 $2N$ 的线性数组：$A[i + N] = A[i]$；
在展开后的 $2N$ 数组上运行标准区间 DP，计算出所有长度为 $N$ 的子区间的解；
全局最优解即为所有长度恰好为 $N$ 的滑动区间的极值：

\[ \text{Ans} = \min_{0 \le i < N} dp[i][i + N - 1] \]

该技巧完美规避了环形取模边界的复杂分支，将环形问题化归为标准的线性区间 DP。

3. 逆向分治思维：戳气球模型 (LeetCode 312)¶

正向思维的陷阱¶

若正向考虑“先戳破哪只气球”：气球 $k$ 破裂后，其左右两边的气球会发生位移而重新相邻。这导致左右两边的子问题不再独立，后续计算严重依赖已经被戳破的气球历史，彻底丧失无后效性。

逆向思维的破局¶

倒过来看：假设气球 $k$ 是开区间 $(i, j)$ 内最后一个被戳破的气球！

既然 $k$ 是最后一个被戳破的，那么当它被戳破的瞬间，其左右两侧与它相邻的气球必定是区间外边界 $i$ 和 $j$（因为 $(i, j)$ 内部的其他气球早已经全部被戳破了！）；
此时气球 $k$ 提供的金币数固定为 $nums[i] \times nums[k] \times nums[j]$；
更绝妙的是：以 $k$ 为分界点，左子区间 $(i, k)$ 和右子区间 $(k, j)$ 的气球相互完全隔离，各自独立求解！

\[ dp[i][j] = \max_{i < k < j} \Big( dp[i][k] + dp[k][j] + nums[i] \times nums[k] \times nums[j] \Big) \]

#include <vector>
#include <algorithm>

int max_coins(std::vector<int>& nums) {
    int n = nums.size();
    // 添加两侧虚拟边界 1
    std::vector<int> val(n + 2, 1);
    for (int i = 0; i < n; ++i) val[i + 1] = nums[i];

    int m = n + 2;
    std::vector<std::vector<int>> dp(m, std::vector<int>(m, 0));

    // 开区间长度 len 从 3 到 m
    for (int len = 3; len <= m; ++len) {
        for (int i = 0; i <= m - len; ++i) {
            int j = i + len - 1;
            // 枚举最后一个被戳破的气球 k
            for (int k = i + 1; k < j; ++k) {
                int total = dp[i][k] + dp[k][j] + val[i] * val[k] * val[j];
                dp[i][j] = std::max(dp[i][j], total);
            }
        }
    }
    return dp[0][m - 1];
}

4. 区间染色、覆盖与消除模型 (Coloring & Elimination)¶

在处理诸如“打印字符串”、“消除连续相同颜色”等问题时，字符或方块的相同性会引发跨区间的协同效应。

4.1 相同字符的“蹭覆盖”机制 (LeetCode 664 奇怪的打印机)¶

在每次只能打印一段连续相同字符的打印机模型中：

正向思维的后效性：先打印哪一部分会动态遮盖先前的字符，难以正向划分子问题；
逆向解耦：关注右端点 $s[j]$ 何时打印：
最坏情况独立打印：$s[j]$ 单独耗费一次操作打印，$dp[i][j] = dp[i][j - 1] + 1$；
“蹭”同名字符的打印机会：若区间内部存在某个位置 $k \in [i, j - 1]$ 使得 $s[k] == s[j]$，则可以在当初刷 $s[k]$ 时一路长刷到位置 $j$，后续在区间 $[k + 1, j - 1]$ 内打印其他字符时将覆盖掉中间多余的底色。这样 $s[j]$ 相当于被“免费”打印了出来！
状态转移方程： $$dp[i][j] = \min\Big(dp[i][j - 1], \min_{k = i}^{j - 1, s[k] == s[j]} (dp[i][k] + dp[k + 1][j - 1])\Big)$$

4.2 消除合并与外部状态升维 (LeetCode 546 移除盒子)¶

当消除一段元素后，原本被相隔的左右两端同色元素会重新合并时，传统二维 $dp[i][j]$ 将彻底丧失无后效性（因为消除区间 $[i, j]$ 的收益高度依赖外部有多少个同色元素与它拼合）。

升维破局：定义三维状态 $dp[i][j][k]$ 表示在消除区间 $[i, j]$ 时，已知其右侧紧邻着 $k$ 个与 $boxes[j]$ 相同颜色的盒子时能取得的最大收益；
两大决策分支：
直接消除右端：将 $boxes[j]$ 及其右侧跟随的 $k$ 个同色盒子一并消除，获得 $(k + 1)^2$ 分： $$dp[i][j][k] = dp[i][j - 1][0] + (k + 1)^2$$
跨越消除中间异色：在区间 $[i, j - 1]$ 内寻找同样颜色的盒子 $m$（$boxes[m] == boxes[j]$），优先将夹在中间的杂色区间 $[m + 1, j - 1]$ 完全消空（贡献 $dp[m + 1][j - 1][0]$），使得 $boxes[m]$ 能与右侧的 $k + 1$ 个同色盒子合流： $$dp[i][j][k] = \max_{m = i}^{j - 1} \Big(dp[m + 1][j - 1][0] + dp[i][m][k + 1]\Big) \quad (\text{当 } boxes[m] == boxes[j])$$

5. 四边形不等式优化 (Knuth Optimization)¶

决策单调性¶

当费用函数 $\text{cost}(i, j)$ 满足四边形不等式（即交叉优于包含：$\text{cost}(i, j) + \text{cost}(i', j') \le \text{cost}(i', j) + \text{cost}(i, j')$，其中 $i \le i' \le j \le j'$）时，区间的最优分割点 $opt[i][j]$ 具备单调性：

\[ opt[i][j - 1] \le opt[i][j] \le opt[i + 1][j] \]

复杂度飞跃¶

有了这个约束，第三层枚举决策点 $k$ 的范围从整个 $[i, j - 1]$ 缩小到紧致的 $[opt[i][j - 1], opt[i + 1][j]]$。经过平摊分析，总时间复杂度由 $\mathcal{O}(N^3)$ 质跃至 $\mathcal{O}(N^2)$！

6. LeetCode 经典真题精选与题解提示¶

LeetCode 312 - 戳气球 (Burst Balloons) 困难
提示

逆向思维区间 DP 标杆。
- 倒序考虑“最后一个被戳破的气球 $k$”。
- $k$ 将开区间 $(i, j)$ 划分为两个完全解耦的独立子问题 $(i, k)$ 与 $(k, j)$，得分增量为 $val[i] \times val[k] \times val[j]$。
LeetCode 664 - 奇怪的打印机 (Strange Printer) 困难
提示

同色覆盖贪心转移。
- 初始情况：打印 $S[i \dots j]$ 最多需要 $dp[i][j-1] + 1$ 次。
- 若存在分割点 $k \in [i, j-1]$ 满足 $S[k] == S[j]$，则最后位置 $j$ 的字符可以顺带在打印 $S[k]$ 时一并打出，无需额外多打一次，从而优化转移为 $dp[i][k] + dp[k + 1][j - 1]$。
- 预处理去除连续重复字符可有效常数加速。
LeetCode 546 - 移除盒子 (Remove Boxes) 困难
提示

区间 DP 天花板 / 外部状态升维。
- 记忆化搜索 $dfs(i, j, k)$ 表示清除区间 $[i, j]$ 且右侧有 $k$ 个与 $boxes[j]$ 相同颜色的盒子时的最大得分。
- 决策一：直接消除末尾的 $k + 1$ 个盒子，收益 $(k + 1)^2 + dfs(i, j - 1, 0)$；
- 决策二：在 $[i, j - 1]$ 内寻找相同颜色的 $m$，先消空中间的 $[m + 1, j - 1]$，转移为 $dfs(m + 1, j - 1, 0) + dfs(i, m, k + 1)$。
LeetCode 730 - 统计不同回文子序列 (Count Different Palindromic Subsequences) 困难
提示

双端字符匹配与容斥去重。
- 当 $s[i] == s[j] = c$ 时，两侧字符向内包裹会使内部所有不同回文序列数量翻倍（贡献 $2 \times dp[i+1][j-1]$）；
- 精妙去重：考察子区间 $s[i+1 \dots j-1]$ 内部包含字符 $c$ 的个数：
- 内部无 $c$：贡献 $+2$（产生 $c$ 和 $cc$ 两种新形态）；
- 内部恰有 1 个 $c$：贡献 $+1$（产生 $cc$ 一种新形态）；
- 内部有 $\ge 2$ 个 $c$：产生容斥重叠，需减去区间内最左和最右两个 $c$ 之间夹住的方案数。
LeetCode 1547 - 切棍子的最小成本 (Minimum Cost to Cut a Stick) 困难
提示

切点区间 DP / 类似戳气球。
- 将棍子两端 $0$ 与 $n$ 作为哨兵加入切点数组中并升序排序；
- 设 $dp[i][j]$ 为完成切割点序列中第 $i$ 到第 $j$ 个切点之间的棍子所需的最小成本；
- 枚举第一刀落下的切点 $k \in (i, j)$，成本为当前段长 $(cuts[j] - cuts[i]) + dp[i][k] + dp[k][j]$。
LeetCode 1000 - 合并石头的最低成本 (Minimum Cost to Merge Stones) 困难
提示

步长步进区间 DP。
- 每次合并 $K$ 堆，总堆数每次净减少 $K - 1$。因此能够合并为 1 堆的充要条件是 $(N - 1) \pmod{K - 1} == 0$。
- 状态扩展：$dp[i][j][m]$ 表示将区间 $[i, j]$ 合并为 $m$ 堆的最小代价；决策点 $k$ 枚举步长以 $K - 1$ 步进。
LeetCode 516 - 最长回文子序列 (Longest Palindromic Subsequence) 中等
提示

双端字符匹配区间 DP。
- 状态定义：$dp[i][j]$ 表示 $S[i \dots j]$ 的最长回文子序列长度。
- 若 $S[i] == S[j]$：两端字符可直接匹配，$dp[i][j] = dp[i + 1][j - 1] + 2$；
- 若 $S[i] \neq S[j]$：两端不能同时保留，$dp[i][j] = \max(dp[i + 1][j], dp[i][j - 1])$。
LeetCode 486 - 预测赢家 (Predict the Winner) 中等
提示

零和博弈极大极小区间 DP。
- $dp[i][j]$ 表示当前玩家面对剩余区间 $[i, j]$ 时，相对于对手能获得的最大净胜分数差。
- 当前玩家若选左端：净收益为 $nums[i] - dp[i + 1][j]$；若选右端：净收益为 $nums[j] - dp[i][j - 1]$。取二者最大值即可。