题意回顾

求长度为 $n$，每个元素在 $[1, m]$ 间的序列数目，使得序列可以通过若干次"删除两端相等且长度至少为 $2$ 的区间"操作被完全删除。

答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 3000$，$1 \leq m \leq 10^9$。

问题分析

1. 可删除序列的特征

这种序列具有类似合法括号序列的结构，但每个"括号"可以是 $m$ 种不同的"颜色"。

序列可被完全删除的充要条件是：存在一种方式将序列分成若干对 $(i, j)$，满足：

• $a_i = a_j$
• 这些配对形成合法的嵌套结构（无交叉）

换句话说，序列必须能够被解析为一个合法的彩色括号序列。

动态规划解法

状态设计

设 $dp[i][j]$ 表示考虑前 $i$ 个位置，当前有 $j$ 个开括号（未匹配的左括号）未匹配的方案数。

这里 $j$ 表示当前前缀中尚未找到匹配的彩色左括号数量。

转移方程

对于每个状态 $dp[i][j]$，考虑第 $i+1$ 个位置的选择：

1. 新增一个开括号（左括号）：

   • 可以选择任意颜色，有 $m$ 种选择
   • 转移：$dp[i+1][j+1] \leftarrow dp[i+1][j+1] + dp[i][j] \times m$

2. 匹配一个开括号（右括号）：

   • 需要 $j > 0$，即至少有一个未匹配的开括号
   • 可以选择任意一个未匹配的开括号进行匹配，有 $j$ 种选择
   • 转移：$dp[i+1][j-1] \leftarrow dp[i+1][j-1] + dp[i][j] \times j$

初始条件

• $dp[0][0] = 1$（空序列，没有未匹配的括号）
• 其他状态初始为 $0$

最终答案

序列完全匹配的条件是所有开括号都被匹配，即 $j = 0$。

答案：$dp[n][0]$

算法实现

步骤

1. 初始化 $dp[0][0] = 1$
2. 对于 $i$ 从 $0$ 到 $n-1$：
   • 对于 $j$ 从 $0$ 到 $n$：
     • 如果 $dp[i][j] > 0$：
       • 新增开括号：$dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] \times m) \bmod MOD$
       • 匹配开括号：如果 $j > 0$，则 $dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j] \times j) \bmod MOD$
3. 输出 $dp[n][0]$

复杂度分析

• 状态数：$O(n^2)$
• 每个状态转移：$O(1)$
• 总时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

对于 $n \leq 3000$，状态数最多约 $9 \times 10^6$，完全可行。

正确性说明

这种解法正确的原因是：

1. 状态设计合理：$j$ 精确地表示了当前未匹配的开括号数量，这完全对应了序列解析过程中的栈深度。

2. 转移完整：

   • 新增开括号对应在序列中添加一个任意颜色的新元素
   • 匹配开括号对应找到一个与之前某个未匹配元素颜色相同的元素

3. 边界处理正确：

   • 初始状态表示空序列是合法的
   • 最终状态要求所有开括号都被匹配

4. 覆盖所有情况：任何可删除序列都对应一种合法的括号解析方式，反之亦然。

总结

本题的关键在于将可删除序列问题转化为带颜色的合法括号序列计数问题：

1. 核心思路：使用二维DP跟踪未匹配的开括号数量
2. 状态设计：$dp[i][j]$ 表示前 $i$ 个位置有 $j$ 个未匹配开括号
3. 转移策略：每次可以新增开括号或匹配一个开括号
4. 复杂度：$O(n^2)$ 时间，$O(n^2)$ 空间
5. 适用范围：完美匹配 $n \leq 3000$ 的数据范围