区间动态规划例题：统计不同非空回文子序列个数问题（字符集限制版） 题目描述 给定一个字符串 s，由字符 'a', 'b', 'c', 'd' 组成（即字符集大小为4）。要求计算字符串 s 中不同非空回文子序列的个数。由于结果可能很大，将结果对 10^9 + 7 取模。 一个字符串的子序列是通过删除原字符串中一些（可以不删除）字符而不改变剩余字符的相对顺序得到的一个新字符串。如果一个子序列是回文的（正着读和反着读一样），并且该回文子序列是唯一的（即去重），那么它被计入答案。 例如： 输入：s = "bccb" 输出：6 解释：6个不同的非空回文子序列为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。 注意：'ccc' 不是子序列，'bbb' 也不是子序列。 解题思路 这个问题需要统计所有不同的回文子序列。直接枚举所有子序列并检查回文性，复杂度太高（O(2^n)）。我们可以使用区间动态规划来高效解决。 关键观察 对于一个区间 [ i, j ]： 如果 s[ i] != s[ j]，那么区间 [ i, j] 内的回文子序列可以由 [ i+1, j] 和 [ i, j-1] 的回文子序列合并得到，但要减去重复计算的部分 [ i+1, j-1 ]。 如果 s[ i] == s[ j]，情况更复杂。除了包含上述情况，我们还需要考虑以 s[ i] 和 s[ j ] 作为回文子序列两端的情况。但需要小心处理重复计数。 然而，直接定义 dp[ i][ j] 为区间 [ i, j] 内不同回文子序列的个数，在 s[ i] == s[ j] 时，我们可能会重复计算某些子序列。例如，对于 "bccb"，区间 [ 0,3 ] 的回文子序列包含 "b", "c", "bb", "cc", "bcb", "bccb"。当计算整个字符串时，我们需要确保不重复计数。 一个更精细的方法是，我们考虑字符集很小（只有4种字符），我们可以利用下一个匹配位置来避免重复。但这里我们采用一种更清晰的状态定义和转移方法。 状态定义 定义 dp[ i][ j] 为字符串 s 在区间 [ i, j ] 内的不同回文子序列的个数。 状态转移方程 我们需要考虑区间 [ i, j] 的两端字符 s[ i] 和 s[ j ] 是否相等。 如果 s[ i] != s[ j ]： 那么区间 [ i, j] 内的所有回文子序列要么包含 s[ i] 但不包含 s[ j]，要么包含 s[ j] 但不包含 s[ i ]，要么两个都不包含。但两个都包含的不可能是回文子序列（因为两端字符不同）。 所以，我们可以从三个更小的区间得到： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] 这里减去 dp[ i+1][ j-1 ] 是因为它被前两项重复计算了（即两个都不包含的子序列）。 如果 s[ i] == s[ j ]： 设 c = s[ i] = s[ j ]。 此时，情况更丰富： a) 首先，包含所有 [ i+1, j-1 ] 内的回文子序列。 b) 其次，考虑以 c 作为回文子序列的两端。对于 [ i+1, j-1] 内的每一个回文子序列，我们在其两端加上 c，仍然是一个回文子序列。但注意，即使 [ i+1, j-1 ] 内没有回文子序列（即空序列），我们加上两个 c 后，得到 "cc" 也是一个新的回文子序列。此外，单个 c 本身也是一个回文子序列，但我们需要确保不重复计算。 更精确地，当 s[ i] == s[ j ] 时： 我们仍然有基础部分：dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1]（即 s[ i] 和 s[ j ] 不同时的情况）。 此外，我们需要加上所有由 [ i+1, j-1] 内的回文子序列两端添加 c 后形成的新回文子序列。注意，即使 [ i+1, j-1 ] 内没有回文子序列，我们也可以形成两个新的回文子序列："c" 和 "cc"？但这里需要仔细处理。 实际上，一个更简洁的转移方式是： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] （基础部分，避免重复） + (dp[ i+1][ j-1] + 1) （新增部分：对于 [ i+1, j-1 ] 内的每个回文子序列，两端加 c 得到新序列；另外，单独两个 c 组成的 "cc" 也可以看作是由空序列两端加 c 得到，而空序列我们通常不计入 dp，所以这里 +1 是表示空序列的情况？但空序列本身不是非空回文，所以我们需要重新思考） 让我们重新思考：当 s[ i] == s[ j ] 时，新增加的回文子序列包括： 单个字符 c（如果之前没有出现过？但可能会重复计数） 以及所有形如 c + X + c 的序列，其中 X 是 [ i+1, j-1 ] 内的任意回文子序列（包括空序列，此时为 "cc"）。 但是，单个字符 c 可能已经在 [ i+1, j-1 ] 的计数中出现过了？是的，所以如果我们直接加，会重复计数。 为了避免重复，我们可以这样考虑：设区间 [ i, j ] 内，以字符 c 开头和结尾的回文子序列的个数为 f(i, j, c)。但这样状态维度会增加。 一个巧妙的解法是：当 s[ i] == s[ j] 时，我们考虑区间 [ i, j ] 内第一个等于 c 的字符的位置 low 和最后一个等于 c 的字符的位置 high。 如果 low > high，即区间 [ i, j ] 内部没有字符 c，那么新增加的回文子序列只有两个："c" 和 "cc"。 如果 low == high，即区间 [ i, j ] 内部只有一个字符 c，那么新增加的回文子序列有："c" 和 "cc"（但 "c" 可能已经算过？需要仔细分析）。 如果 low < high，即区间 [ i, j] 内部至少有两个字符 c，那么我们需要考虑区间 [ low+1, high-1 ] 内的回文子序列，以避免重复。 实际上，一个标准且正确的状态转移方程是： if s[ i] != s[ j ]: dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] else: 令 low = i+1 之后第一个等于 s[ i] 的字符的位置，high = j-1 之前最后一个等于 s[ i ] 的字符的位置。 if low > high: // 内部没有相同字符 dp[ i][ j] = dp[ i+1][ j-1] * 2 + 2 elif low == high: // 内部恰好一个相同字符 dp[ i][ j] = dp[ i+1][ j-1] * 2 + 1 else: // low < high, 内部至少两个相同字符 dp[ i][ j] = dp[ i+1][ j-1] * 2 - dp[ low+1][ high-1 ] 解释： 当 s[ i] == s[ j] 时，区间 [ i, j ] 的回文子序列包括： 不包含 s[ i] 和 s[ j] 的：即 [ i+1, j-1] 内的所有回文子序列，共 dp[ i+1][ j-1 ] 个。 包含 s[ i] 但不包含 s[ j] 的：实际上这部分已经包含在 dp[ i][ j-1] - dp[ i+1][ j-1 ] 中，但我们的转移方程不直接这样加。 实际上，更直接的想法是：所有回文子序列可以分为两类：包含两端字符 c 的，和不包含的。 不包含的：有 dp[ i+1][ j-1 ] 个。 包含的：对于 [ i+1, j-1] 内的每一个回文子序列，我们在其两端加上 c，都构成一个新的回文子序列。所以也有 dp[ i+1][ j-1] 个。但这里有一个问题：新产生的序列可能和已有的重复吗？例如，如果 [ i+1, j-1] 内已经有一个回文子序列 "c"，我们两端加 c 得到 "ccc"，但 "c" 本身已经存在。注意，我们统计的是不同的子序列，所以 "c" 和 "ccc" 是不同的，不会重复。但是，如果 [ i+1, j-1 ] 内已经有 "cc"，我们两端加 c 得到 "cccc"，这也是不同的。所以看起来不会重复。 但是，还有一种特殊情况：单个字符 c 本身。当我们用空序列两端加 c，得到 "cc"，但单个 c 呢？实际上，空序列两端加 c 得到 "cc"，而单个 c 可以通过在空序列的一端加 c 得到？不，我们的操作是两端加 c，所以空序列只能得到 "cc"，不能得到 "c"。那么 "c" 是怎么来的？它应该已经包含在 [ i+1, j-1] 的回文子序列中了吗？不一定，如果 [ i+1, j-1 ] 内没有字符 c，那么 "c" 就不会被计算。 因此，我们需要额外考虑由两个端点的 c 形成的新回文子序列：即 "c" 和 "cc"。 如果 [ i+1, j-1 ] 内没有字符 c（即 low > high），那么 "c" 和 "cc" 都是全新的，所以加2。 如果 [ i+1, j-1] 内有一个字符 c（即 low == high），那么 "c" 已经存在于 [ i+1, j-1] 的回文子序列中（因为单个字符 c 是回文），所以当我们用空序列两端加 c 得到 "cc" 是新的，但 "c" 是重复的？不，我们考虑的是包含两端 c 的新序列：对于 [ i+1, j-1] 内的每一个回文子序列，两端加 c 都得到一个新序列。当 [ i+1, j-1 ] 内有一个 c 时，空序列两端加 c 得到 "cc"（新），而单个 c 两端加 c 得到 "ccc"（新）。但 "c" 本身呢？它并不是由两端加 c 得到的（因为两端加 c 得到的序列长度至少为2）。所以实际上，我们仍然需要额外添加两个序列："c" 和 "cc"？但这样会重复吗？ 实际上，标准解法中，当 s[ i] == s[ j ] 时： dp[ i][ j] = 2 * dp[ i+1][ j-1 ] + (如果内部没有相同字符，加2；如果内部有一个相同字符，加1；如果内部有多个相同字符，减去内部中间部分的重复计数)。 这个方法的正确性在于： 不包含两端字符的回文子序列有 dp[ i+1][ j-1 ] 个。 包含两端字符的回文子序列，可以通过在 [ i+1, j-1] 内的每个回文子序列两端加 c 得到，所以也有 dp[ i+1][ j-1] 个。但这样计算可能会包含重复的序列吗？是的，如果 [ i+1, j-1 ] 内部有相同的字符 c，那么某些以 c 开头和结尾的子序列可能会被重复计算。 具体来说： 如果 [ i+1, j-1] 内没有字符 c（low > high），那么所有新产生的序列都是新的，所以总数为 2 * dp[ i+1][ j-1 ] + 2（加2是因为单独由两个端点可以形成 "c" 和 "cc"？但注意，当我们用空序列两端加 c，得到 "cc"，而 "c" 并没有被产生？所以这里需要额外加2来包括 "c" 和 "cc"）。 如果 [ i+1, j-1] 内有一个字符 c（low == high），那么 "c" 这个子序列已经包含在 [ i+1, j-1 ] 的计数中了（因为单个字符 c 是回文），所以当我们两端加 c 时，不会产生新的 "c"，但会产生 "cc" 和 "ccc" 等。但实际上，我们只需要额外加1（即 "cc"），因为 "c" 已经算过了。 如果 [ i+1, j-1] 内有多个字符 c（low < high），那么某些序列会被重复计算。具体来说，区间 [ low+1, high-1] 内的回文子序列，当两端加 c 后，会与直接由区间 [ i+1, j-1] 两端加 c 产生的序列重复？实际上，重复的部分正是由 [ low+1, high-1] 内的回文子序列两端加 c 后产生的序列，因为这些序列已经包含在 [ i+1, j-1] 两端加 c 产生的序列中了。所以我们需要减去这部分重复计数，即 dp[ low+1][ high-1 ]。 初始化 对于长度为1的区间（即 i == j），只有一个字符，回文子序列个数为1（即该字符本身）。 对于空区间（i > j），回文子序列个数为0（因为题目要求非空）。 计算顺序 按区间长度从小到大计算。 示例演示 以 s = "bccb" 为例： 初始化：所有长度为1的区间 dp[ i][ i ] = 1。 长度2： 区间 [ 0,1]: s[ 0]='b', s[ 1]='c'，不同，dp[ 0][ 1] = dp[ 1][ 1] + dp[ 0][ 0] - dp[ 1][ 0 ] = 1 + 1 - 0 = 2。 区间 [ 1,2]: s[ 1]='c', s[ 2]='c'，相同。low 为1之后第一个'c'是位置2？不，对于区间 [ 1,2]，i=1, j=2, 内部区间 [ 2,1] 为空，所以 low 和 high 怎么找？我们需要在 (i, j) 即 (1,2) 之间找字符 'c'。区间 (1,2) 是开区间，没有整数位置，所以 low > high，因此 dp[ 1][ 2] = 2 * dp[ 2][ 1] + 2 = 2* 0 + 2 = 2。 区间 [ 2,3]: s[ 2]='c', s[ 3]='b'，不同，dp[ 2][ 3] = dp[ 3][ 3] + dp[ 2][ 2] - dp[ 3][ 2 ] = 1 + 1 - 0 = 2。 长度3： 区间 [ 0,2]: s[ 0]='b', s[ 2]='c'，不同，dp[ 0][ 2] = dp[ 1][ 2] + dp[ 0][ 1] - dp[ 1][ 1 ] = 2 + 2 - 1 = 3。 区间 [ 1,3]: s[ 1]='c', s[ 3]='b'，不同，dp[ 1][ 3] = dp[ 2][ 3] + dp[ 1][ 2] - dp[ 2][ 2 ] = 2 + 2 - 1 = 3。 长度4： 区间 [ 0,3]: s[ 0]='b', s[ 3]='b'，相同。在 (0,3) 即位置1,2中找字符 'b'。第一个 'b' 在位置0，最后一个在位置3，但内部区间 (0,3) 没有 'b'（因为s[ 1]和s[ 2]是'c'），所以 low > high。因此 dp[ 0][ 3] = 2 * dp[ 1][ 2] + 2 = 2* 2 + 2 = 6。 最终结果 dp[ 0][ 3 ] = 6，符合示例输出。 复杂度分析 时间复杂度：O(n^2)，需要填充一个 n x n 的DP表。 空间复杂度：O(n^2)，用于存储DP表。 代码实现要点 需要预处理每个区间内第一个和最后一个特定字符的位置，但我们可以动态查找。 注意取模。 这个解法巧妙地处理了重复计数的问题，适用于小字符集的字符串。