题源链接：洛谷 P17015 [GESP202606 七级] 消消乐

---

一、背景

在算法竞赛的动态规划专题中，有一类问题特别考验选手的"逆向思维"——它们不问你"第一步该怎么做"，而是逼着你思考"最后一步发生了什么"。GESP 七级的这道消消乐题，就是这类问题的典型代表。

题目规则很简单：给定一个数组，每次删除一个元素，得分是该元素两侧相邻元素之和。删到数组为空时，求最大总得分。初看之下，这似乎是一个贪心问题——每次选个"最优"的元素删除？但仔细一想，删除一个元素会改变其他元素的邻居关系，前面的选择会深刻影响后面的得分。这种"牵一发而动全身"的特性，正是区间 DP 大显身手的舞台。

本文就从这道消消乐题出发，聊聊区间动态规划的核心思想，以及最后删除策略这个巧妙的逆向思维技巧。

---

二、核心思想

2.1 为什么贪心会失败？

拿到这道题，很多选手的第一直觉是：每次删除当前"最划算"的元素——也就是两侧邻居之和最大的那个。但这个策略真的最优吗？

举个反例：数组 $[1,100,1,100,1]$。如果贪心先删中间的 $100$（邻居和 $1+1=2$），然后删两边的 $1$（邻居和 $0+100=100$ 和 $100+0=100$），总得分 $2+100+100=202$。但如果先删两边的 $1$，再删中间的 $100$，得分可能完全不同。

问题的本质在于：删除操作会改变数组结构。一个元素现在看起来"不划算"，但删除其他元素后，它可能变成"香饽饽"。这就像下棋——只看眼前一步的贪心，往往会输掉整盘棋。

贪心失效的特征：

• 无后效性被破坏：前面的选择改变后续状态，无法局部最优推导全局最优
• 决策相互依赖：删除顺序形成一个全序关系，每个决策都受之前所有决策影响
• 需要全局视角：必须从整体删除序列的角度评估优劣，而非单步最优

2.2 逆向思维：最后删除谁？

既然正向思考"先删谁"太复杂，不如反过来想：最后一个被删除的元素是谁？

这个逆向视角有一个巨大的优势——当某个元素 $k$ 是区间 $[i,j]$ 中最后一个被删除的元素时，它的左右邻居是确定的：就是区间外的边界元素 $a_{i-1}$ 和 $a_{j+1}$。因为 $[i,j]$ 内的其他元素都已经被删光了，$k$ 孤零零地夹在两个边界之间。

这意味着：最后删除的元素的得分是固定的，不依赖于内部删除顺序！无论你怎么折腾 $[i,j]$ 内的其他元素，最后删 $k$ 时，得分永远是 $a_{i-1}+a_{j+1}$。

我们可以把这个问题想象成拆俄罗斯套娃：

• 最外层是区间 $[i,j]$，边界是 $a_{i-1}$ 和 $a_{j+1}$
• 你一层一层往里拆，最后拆到核心 $k$
• 拆到核心时，得分只取决于最外层的边界，和中间怎么拆无关

2.3 区间 DP 的状态设计

基于"最后删除"的逆向思维，我们定义状态：

$$dp[i][j]=\text{删除区间 }[i,j]\text{ 内所有元素能获得的最大分数}$$

状态转移时，枚举区间 $[i,j]$ 内最后一个被删除的元素 $k$：

d p [ i ] [ j ] = max ⁡ k ∈ [ i , j ] { d p [ i ] [ k − 1 ] + d p [ k + 1 ] [ j ] + a i − 1 + a j + 1 } dp[i][j] = \max_{k \in [i, j]} \left\{ dp[i][k-1] + dp[k+1][j] + a_{i-1} + a_{j+1} \right\} dp[i][j]=k∈[i,j]max​{dp[i][k−1]+dp[k+1][j]+ai−1​+aj+1​}

其中：

• $dp[i][k-1]$：先删除 $k$ 左边的所有元素
• $dp[k+1][j]$：再删除 $k$ 右边的所有元素
• $a_{i-1}+a_{j+1}$：最后删除 $k$ 的固定得分

这就像把一个大区间劈成左右两个小区间，各自独立求解，最后加上"收尾"的固定奖励。

---

三、算法模板

3.1 算法到底在干什么？——直觉解释

我们的算法是一台"区间拆解机"：

1. 从小区间开始：先解决长度为 $1$ 的区间（只删一个元素，得分就是它的两个邻居）
2. 逐步扩展：按长度从小到大，解决越来越大的区间
3. 枚举收尾人：对于每个区间，枚举"最后删谁"，把问题拆成左右两个子区间
4. 取最优组合：所有可能的"收尾人"中，选择总得分最大的那个

整个过程就像拼图游戏：先把小碎片拼好，再用小碎片拼大碎片，直到拼出完整的图案。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 区间DP消消乐(a[1..n]):
    // 边界虚拟元素
    a[0] = 0, a[n+1] = 0

    // 初始化：长度为 1 的区间
    for i = 1 to n:
        dp[i][i] = a[i-1] + a[i+1]

    // 枚举区间长度
    for len = 2 to n:
        for i = 1 to n-len+1:
            j = i + len - 1
            dp[i][j] = 0
            for k = i to j:
                // 最后删除 k，得分固定为 a[i-1] + a[j+1]
                dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + a[i-1] + a[j+1])

    return dp[1][n]

实战代码（通用模板）：

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;

int n;
int a[N];
int dp[N][N];

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // 初始化：区间长度为 1
    for (int i = 1; i <= n; i++)
        dp[i][i] = a[i - 1] + a[i + 1];

    // 区间 DP：按长度从小到大枚举
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            for (int k = i; k <= j; k++)
            {
                // 最后删除 k，左右子区间独立求解
                dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + a[i - 1] + a[j + 1]);
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

3.3 例题实现 —— 本题完整代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;                 // 常量：最大数组长度

int n;                             // n: 数组长度
int a[N];                          // a[i]: 数组元素，a[0] 和 a[n+1] 视为边界（值为0）
int dp[N][N];                      // dp[i][j]: 删除区间 [i,j] 内所有元素能获得的最大分数

signed main()
{
    cin >> n;                      // 读入数组长度

    for (int i = 1; i <= n; i++)  // 读入数组元素
        cin >> a[i];

    for (int i = 1; i <= n; i++)  // 初始化：区间长度为 1 的情况
        dp[i][i] = a[i - 1] + a[i + 1];  // 删除单个元素 i，得分 = 左侧相邻 + 右侧相邻

    for (int len = 2; len <= n; len++)  // 枚举区间长度，从 2 到 n
    {
        for (int i = 1; i + len - 1 <= n; i++)  // 枚举区间左端点
        {
            int j = i + len - 1;    // j: 区间右端点

            for (int k = i; k <= j; k++)  // 枚举区间内最后一个被删除的元素 k
            {
                // 状态转移：先删除 [i,k-1] 和 [k+1,j] 内的元素，最后删除 k
                // 最后删除 k 时，其相邻元素为 a[i-1] 和 a[j+1]（区间外的边界元素）
                dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + a[i - 1] + a[j + 1]);
            }
        }
    }

    cout << dp[1][n] << endl;      // 输出删除整个数组 [1,n] 的最大分数

    return 0;
}

3.4 对比实现 —— 其他路径的探讨

区间 DP 是解决这类问题的标准方法，但在不同场景下还有其他思路值得了解：

方案	核心思想	时间复杂度	适用场景
区间 DP + 最后删除（本题做法）	逆向思维，枚举最后删除元素	$O(n^3)$	删除顺序影响得分的区间问题
记忆化搜索	递归实现区间 DP，自顶向下	$O(n^3)$	代码更直观，但常数较大
贪心 + 证明	寻找特定结构下的贪心策略	$O(n)$ 或 $O(n\log n)$	需要题目有更强的结构性
树形 DP 转化	将删除序列看作一棵笛卡尔树	$O(n^2)$	适用于有优先级约束的删除问题

对于本题，$n\le 100$ 的数据范围使得 $O(n^3)$ 的区间 DP 完全够用。如果 $n$ 更大（如 $10^3$ 级别），可能需要寻找更优的算法或优化状态转移。

3.5 变体清单 —— 常见变形

变体类型	题目描述	关键变化	解法调整
得分改为乘积	删除得分改为两侧邻居之积	目标函数变化	状态转移中的加法变乘法，max 可能变 min
指定删除顺序约束	某些元素必须在其他元素之前删除	增加偏序约束	在状态中增加已删除集合（状压 DP）
环形数组	数组首尾相连	边界条件变化	破环成链，枚举断点，做 $n$ 次区间 DP
多组询问	多次询问子区间的最大得分	需要快速回答	预处理所有区间 DP 值，$O(1)$ 回答
带权删除代价	删除每个元素有额外代价	目标函数变化	状态转移中增加代价项
保留 $k$ 个元素	不要求删完，保留 $k$ 个	终止条件变化	修改 DP 目标，或转化为删除 $n-k$ 个

3.6 什么时候不能用？——边界条件和反例

区间 DP 虽然强大，但也有其适用范围和边界：

• $n$ 过大时：$O(n^3)$ 的复杂度在 $n=10^3$ 时达到 $10^9$，可能超时。此时需要寻找更优算法或优化技巧（如四边形不等式优化）。
• 状态维度爆炸：如果问题需要在状态中记录更多信息（如已删除的具体集合），状态空间可能指数级增长，不适合区间 DP。
• 不满足最优子结构：如果子问题的最优解不能组合成原问题的最优解，区间 DP 失效。例如，如果删除某个元素会影响多个不相交区间的得分关联。
• 边界处理错误：忘记设置虚拟边界 $a[0]=a[n+1]=0$ 是常见错误。当区间延伸到数组边界时，不存在的邻居应视为 $0$。
• 初始化遗漏：长度为 $1$ 的区间初始化必须正确，否则后续状态转移会基于错误的基础值。

---

四、底层逻辑

4.1 为什么"最后删除"的得分是固定的？

这是本题最关键的性质，值得单独证明。

考虑区间 $[i,j]$ 和其中某个元素 $k$。假设 $k$ 是 $[i,j]$ 中最后一个被删除的元素。当删除 $k$ 时：

• $[i,j]$ 中除 $k$ 外的所有元素都已被删除
• 因此 $k$ 的左侧邻居只能是 $a_{i-1}$（$i$ 左边的第一个元素，或虚拟边界 $0$）
• $k$ 的右侧邻居只能是 $a_{j+1}$（$j$ 右边的第一个元素，或虚拟边界 $0$）

所以删除 $k$ 的得分固定为 $a_{i-1}+a_{j+1}$，与 $k$ 在 $[i,j]$ 内的具体位置无关，也与 $[i,j]$ 内其他元素的删除顺序无关。

这个性质的威力在于：它将一个看似与顺序强相关的问题，转化为了可以分治的子问题。左右子区间的删除互不影响，各自独立取最优即可。

4.2 与经典问题的对比

这道题和经典的区间 DP 问题家族有密切联系：

问题	核心操作	状态设计	时间复杂度
矩阵链乘法	选择最后相乘的位置	$dp[i][j]=\min$ 分割点	$O(n^3)$
石子合并	选择最后合并的堆	$dp[i][j]=\max$ 分割点 + 合并代价	$O(n^3)$
本题：消消乐	选择最后删除的元素	$dp[i][j]=\max$ 分割点 + 固定得分	$O(n^3)$
括号匹配	选择最后匹配的括号	$dp[i][j]$ 由 $dp[i+1][j-1]$ 转移	$O(n^3)$
最优二叉搜索树	选择根结点	$dp[i][j]=\min$ 根 + 左右子树	$O(n^3)$

可以看到，这些问题的共同特征是：通过枚举"最后一步"的选择，将大问题分解为两个独立的小问题。这种"最后一步"的逆向思维，是区间 DP 的灵魂。

4.3 隐含约束的分析

题目中有几个容易被忽略但至关重要的细节：

• 非负整数：数组元素是非负整数，这意味着得分不会为负，保证了"最大得分"的合理性。如果有负数，可能需要考虑"不删"或"少删"的策略。
• 数组变空：必须删除所有元素，不能只删一部分。这保证了 DP 的终止条件是明确的。
• 虚拟边界：$a_0$ 和 $a_{n+1}$ 视为 $0$，这是处理边界邻居的关键。如果不设虚拟边界，需要大量的特判。
• $n$ 的范围：虽然题目未明确给出，但从代码的 $N=105$ 可以推断 $n\le 100$ 左右，$O(n^3)$ 完全可行。

---

五、决策表

面对"删除/合并/分割序列，求最优得分"类问题，如何快速选型？

场景特征	推荐方案	时间复杂度	备注
删除顺序影响得分，最后操作得分固定	区间 DP + 最后删除枚举	$O(n^3)$	最通用，适用于大多数序列删除问题
相邻元素合并，合并代价与顺序无关	区间 DP + 贪心（如 Huffman）	$O(n\log n)$	如石子合并的变种
需要记录已删除集合	状压 DP	$O(2^n\cdot n)$	$n\le 20$ 时可用
有优先级/依赖约束	树形 DP / 拓扑排序	$O(n)$ 或 $O(n^2)$	先建依赖图
环形结构	破环成链 + 区间 DP	$O(n^3)$	枚举断点，做 $n$ 次 DP
在线查询子区间	预处理所有区间 DP	$O(n^3)$ 预处理，$O(1)$ 查询	空间换时间

一句话总结：序列操作想区间，最后一步是关键；子问题独立则 DP，相互依赖想状压。

---

六、工程视角

区间 DP 和"最后删除"的思想在实际工程中有着广泛的应用：

1. 编译器优化：表达式求值顺序：编译器在生成代码时，需要决定表达式中运算的求值顺序。对于具有结合律的运算，不同的求值顺序可能影响寄存器使用和缓存效率。区间 DP 可以用来寻找最优的求值顺序，类似于矩阵链乘法的优化。

2. 数据库查询优化：在关系型数据库中，多表连接的顺序会显著影响查询性能。将表连接视为"合并"操作，连接代价视为"得分"，可以用区间 DP 的思想寻找最优连接顺序（虽然实际数据库通常用启发式算法，但小规模场景下 DP 是最优解）。

3. 文件系统碎片整理：磁盘上的文件块可能需要重新排列以减少寻道时间。将碎片整理视为"删除和重组"的过程，相邻块的关系影响整理代价，可以用类似的区间优化思想来规划整理策略。

4. 任务调度与资源释放：在操作系统中，进程释放资源时，释放顺序可能影响系统的整体性能（如缓存命中率、内存碎片等）。如果释放某个资源时，其"邻居"资源的状态影响得分/代价，就可以用区间 DP 来规划最优释放顺序。

---

七、小结

本文从一道 GESP 七级真题出发，探讨了区间动态规划与最后删除策略这对经典组合。

核心认知可以总结为：

当操作的顺序影响最终结果，但"最后一步"的代价可以独立于内部顺序确定时，逆向思考、枚举最后操作，是区间 DP 最优雅的切入点。

用公式化的语言概括：

d p [ i ] [ j ] = max ⁡ k ∈ [ i , j ] { d p [ i ] [ k − 1 ] + d p [ k + 1 ] [ j ] + a i − 1 + a j + 1 } dp[i][j] = \max_{k \in [i, j]} \left\{ dp[i][k-1] + dp[k+1][j] + a_{i-1} + a_{j+1} \right\} dp[i][j]=k∈[i,j]max​{dp[i][k−1]+dp[k+1][j]+ai−1​+aj+1​}

这道题教会我们的，不仅是如何写三重循环和状态转移方程，更是一种**“逆向拆解问题”**的思维习惯：在算法竞赛中，当正向思考"第一步怎么做"陷入困境时，不妨反过来想想"最后一步发生了什么"。很多时候，最后一步的确定性会为整个问题打开突破口。这种"从终点出发"的思维路径，是动态规划中最具美感的解题策略之一。

---

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区留言交流。