区间动态规划例题：统计不同非空回文子序列个数问题（字符集限制版）
字数 2381 2025-11-05 08:31:05

区间动态规划例题：统计不同非空回文子序列个数问题（字符集限制版）

题目描述：
给定一个字符串 s，由字符 'a', 'b', 'c', 'd' 四种字符组成（即字符集大小为4），长度不超过1000。要求统计 s 中不同非空回文子序列的个数。由于答案可能很大，返回结果对 10^9 + 7 取模。

注意：子序列是通过删除原字符串某些字符（可以不删除）而不改变剩余字符相对顺序形成的新字符串。如果某个回文子序列在内容上相同，即使来自原字符串的不同位置，也视为同一个子序列。

解题过程循序渐进讲解

步骤1：理解问题核心
我们需要统计所有不同的回文子序列。例如 s = "bccb"，回文子序列有：
"b", "c", "bb", "cc", "bcb", "bccb"（注意"ccc"不是回文，"bcb"出现多次但只算一次）。
关键点：不同位置但内容相同的子序列视为同一个。

步骤2：确定DP状态定义
定义 dp[i][j] 表示在子串 s[i..j] 中，所有不同非空回文子序列的个数。
但这样定义会重复计算相同内容但不同位置的子序列，不符合"不同"的要求。

正确状态定义：
设 dp[i][j] 表示在子串 s[i..j] 中，以 s[i] 开头且以 s[j] 结尾的所有不同回文子序列的个数。
但这样还不能直接得到最终答案，需要更精细的状态设计。

步骤3：引入字符维度
由于字符集只有4种，我们可以增加一维表示回文子序列的两端字符：
定义 dp[i][j][c] 表示在子串 s[i..j] 中，以字符 c 开头且以字符 c 结尾的所有不同回文子序列的个数（c ∈ {'a','b','c','d'}）。

最终答案 = Σ dp[0][n-1][c] 对所有字符 c 求和。

步骤4：状态转移分析
考虑子串 s[i..j]，对于每个字符 c：

  1. 如果 s[i] ≠ c 或 s[j] ≠ c：
    dp[i][j][c] = dp[i+1][j][c] 或 dp[i][j-1][c] 或 dp[i+1][j-1][c]？需要仔细分析。

实际上更精确的状态转移：

  • 如果 s[i] ≠ c：dp[i][j][c] = dp[i+1][j][c]
  • 如果 s[j] ≠ c：dp[i][j][c] = dp[i][j-1][c]
  • 如果 s[i] ≠ c 且 s[j] ≠ c：dp[i][j][c] = dp[i+1][j-1][c] + 调整项

步骤5：完整状态转移方程
定义 f[i][j] 表示子串 s[i..j] 中所有不同回文子序列的个数（这就是最终答案对应的状态）。

我们有：

  1. f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]（容斥原理，减去重复部分）
  2. 如果 s[i] == s[j]：
    设 c = s[i]，那么以 c 开头和结尾的回文子序列包括：
    • 单个字符 c（1个）
    • c + (s[i+1..j-1] 中的任意回文子序列) + c
      所以新增的回文子序列个数 = f[i+1][j-1] + 1
      因此：f[i][j] += f[i+1][j-1] + 1

但要避免重复计数，需要更精细的处理。

步骤6：避免重复计数的标准解法
标准解法使用二维DP，但记录每个字符最近出现的位置：

设 dp[i][j] 表示 s[i..j] 中不同回文子序列的个数。
转移方程：
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]（容斥原理）

如果 s[i] == s[j]：
令 left = 下一个等于 s[i] 的位置（i < left < j）
令 right = 前一个等于 s[j] 的位置（i < right < j）

如果 left > right：说明中间没有相同的字符
dp[i][j] += dp[i+1][j-1] + 1

如果 left == right：说明中间有一个相同的字符
dp[i][j] += dp[i+1][j-1] + 1

如果 left < right：说明中间有多个相同的字符
dp[i][j] += dp[left+1][right-1] + 1

步骤7：算法实现步骤

  1. 预处理每个字符在每个区间内的第一次和最后一次出现位置
  2. 按区间长度从小到大计算DP
  3. 对每个区间 [i, j]，先计算基础值（容斥原理）
  4. 如果 s[i] == s[j]，根据中间相同字符的情况调整
  5. 结果取模

步骤8：示例演示
s = "bccb"

计算过程：

  • 区间长度1：dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1
  • 区间长度2：
    [0,1]："b","c" → dp=2
    [1,2]："c","c" → 中间无相同字符，dp=2+dp[2][1]+1=2+0+1=3
    [2,3]："c","b" → dp=2
  • 区间长度3：
    [0,2]：s[0]≠s[2]，dp=dp[1][2]+dp[0][1]-dp[1][1]=3+2-1=4
    [1,3]：s[1]=s[3]='c'，中间有相同字符，需要特殊处理...
  • 最终得到 dp[0][3] = 6

步骤9：复杂度分析
时间复杂度：O(n²)
空间复杂度：O(n²)

这种方法确保了相同内容的回文子序列只被统计一次，符合题目要求。

区间动态规划例题：统计不同非空回文子序列个数问题（字符集限制版） 题目描述： 给定一个字符串 s，由字符 'a', 'b', 'c', 'd' 四种字符组成（即字符集大小为4），长度不超过1000。要求统计 s 中不同非空回文子序列的个数。由于答案可能很大，返回结果对 10^9 + 7 取模。 注意：子序列是通过删除原字符串某些字符（可以不删除）而不改变剩余字符相对顺序形成的新字符串。如果某个回文子序列在内容上相同，即使来自原字符串的不同位置，也视为同一个子序列。 解题过程循序渐进讲解 步骤1：理解问题核心 我们需要统计所有不同的回文子序列。例如 s = "bccb"，回文子序列有： "b", "c", "bb", "cc", "bcb", "bccb"（注意"ccc"不是回文，"bcb"出现多次但只算一次）。 关键点：不同位置但内容相同的子序列视为同一个。 步骤2：确定DP状态定义 定义 dp[ i][ j] 表示在子串 s[ i..j ] 中，所有不同非空回文子序列的个数。 但这样定义会重复计算相同内容但不同位置的子序列，不符合"不同"的要求。 正确状态定义： 设 dp[ i][ j] 表示在子串 s[ i..j] 中，以 s[ i] 开头且以 s[ j ] 结尾的所有不同回文子序列的个数。 但这样还不能直接得到最终答案，需要更精细的状态设计。 步骤3：引入字符维度 由于字符集只有4种，我们可以增加一维表示回文子序列的两端字符： 定义 dp[ i][ j][ c] 表示在子串 s[ i..j ] 中，以字符 c 开头且以字符 c 结尾的所有不同回文子序列的个数（c ∈ {'a','b','c','d'}）。 最终答案 = Σ dp[ 0][ n-1][ c ] 对所有字符 c 求和。 步骤4：状态转移分析 考虑子串 s[ i..j ]，对于每个字符 c： 如果 s[ i] ≠ c 或 s[ j ] ≠ c： dp[ i][ j][ c] = dp[ i+1][ j][ c] 或 dp[ i][ j-1][ c] 或 dp[ i+1][ j-1][ c ]？需要仔细分析。 实际上更精确的状态转移： 如果 s[ i] ≠ c：dp[ i][ j][ c] = dp[ i+1][ j][ c ] 如果 s[ j] ≠ c：dp[ i][ j][ c] = dp[ i][ j-1][ c ] 如果 s[ i] ≠ c 且 s[ j] ≠ c：dp[ i][ j][ c] = dp[ i+1][ j-1][ c ] + 调整项 步骤5：完整状态转移方程 定义 f[ i][ j] 表示子串 s[ i..j ] 中所有不同回文子序列的个数（这就是最终答案对应的状态）。 我们有： f[ i][ j] = f[ i+1][ j] + f[ i][ j-1] - f[ i+1][ j-1 ]（容斥原理，减去重复部分） 如果 s[ i] == s[ j ]： 设 c = s[ i ]，那么以 c 开头和结尾的回文子序列包括： 单个字符 c（1个） c + (s[ i+1..j-1 ] 中的任意回文子序列) + c 所以新增的回文子序列个数 = f[ i+1][ j-1 ] + 1 因此：f[ i][ j] += f[ i+1][ j-1 ] + 1 但要避免重复计数，需要更精细的处理。 步骤6：避免重复计数的标准解法 标准解法使用二维DP，但记录每个字符最近出现的位置： 设 dp[ i][ j] 表示 s[ i..j ] 中不同回文子序列的个数。 转移方程： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ]（容斥原理） 如果 s[ i] == s[ j ]： 令 left = 下一个等于 s[ i] 的位置（i < left < j） 令 right = 前一个等于 s[ j] 的位置（i < right < j） 如果 left > right：说明中间没有相同的字符 dp[ i][ j] += dp[ i+1][ j-1 ] + 1 如果 left == right：说明中间有一个相同的字符 dp[ i][ j] += dp[ i+1][ j-1 ] + 1 如果 left < right：说明中间有多个相同的字符 dp[ i][ j] += dp[ left+1][ right-1 ] + 1 步骤7：算法实现步骤 预处理每个字符在每个区间内的第一次和最后一次出现位置 按区间长度从小到大计算DP 对每个区间 [ i, j ]，先计算基础值（容斥原理） 如果 s[ i] == s[ j ]，根据中间相同字符的情况调整 结果取模 步骤8：示例演示 s = "bccb" 计算过程： 区间长度1：dp[ 0][ 0]=1, dp[ 1][ 1]=1, dp[ 2][ 2]=1, dp[ 3][ 3 ]=1 区间长度2： [ 0,1 ]："b","c" → dp=2 [ 1,2]："c","c" → 中间无相同字符，dp=2+dp[ 2][ 1 ]+1=2+0+1=3 [ 2,3 ]："c","b" → dp=2 区间长度3： [ 0,2]：s[ 0]≠s[ 2]，dp=dp[ 1][ 2]+dp[ 0][ 1]-dp[ 1][ 1 ]=3+2-1=4 [ 1,3]：s[ 1]=s[ 3 ]='c'，中间有相同字符，需要特殊处理... 最终得到 dp[ 0][ 3 ] = 6 步骤9：复杂度分析 时间复杂度：O(n²) 空间复杂度：O(n²) 这种方法确保了相同内容的回文子序列只被统计一次，符合题目要求。