最长回文子序列的变种：统计不同非空回文子序列的个数

字数 1907 2025-11-05 08:31:05

最长回文子序列的变种：统计不同非空回文子序列的个数

题目描述
给定一个字符串 s，要求统计其中所有不同的非空回文子序列的个数。注意，这里的子序列是指从原字符串中删除零个或多个字符后，剩余字符相对位置不变形成的序列。由于不同位置的相同字符序列被视为同一个子序列，因此需要去重。结果可能很大，需要对 10^9 + 7 取模。

例如，对于字符串 s = "bccb"，不同的非空回文子序列有："b", "c", "bb", "cc", "bcb", "bccb"，共 6 个。

解题思路
这是一个线性动态规划问题，关键在于如何避免重复计数。我们可以使用区间动态规划，定义 dp[i][j] 为字符串 s[i..j] 中不同回文子序列的个数。但直接统计会重复计算相同字符组成的子序列。因此，需要记录每个字符首次和最后一次出现的位置，确保在统计时每个字符组合只被计算一次。

详细步骤

定义状态
设 dp[i][j] 表示子串 s[i..j] 中不同回文子序列的个数。目标是求 dp[0][n-1]，其中 n 是字符串长度。
状态转移
考虑子串 s[i..j]：
- 如果 s[i] != s[j]：
  回文子序列要么包含 s[i] 但不包含 s[j]，要么包含 s[j] 但不包含 s[i]，要么两者都不包含。但直接使用 dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] 会减去中间部分两次，需要加回。
  转移方程：
  dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
- 如果 s[i] == s[j]（设字符为 ch）：
  此时，所有 s[i+1..j-1] 中的回文子序列，两端加上 ch 后仍是回文子序列。此外，还需考虑单独由 ch 组成的子序列（如 "ch" 或 "chch"）。
  但需避免重复：如果在 s[i+1..j-1] 中存在同样以 ch 开头和结尾的子序列，可能会重复计算。
  解决方法是找到子串 s[i+1..j-1] 中第一个等于 ch 的位置 left 和最后一个等于 ch 的位置 right：
  - 如果 left > right：说明中间没有字符 ch，新增的子序列是 ch 和 chch。
    转移方程：
    dp[i][j] = dp[i+1][j-1] * 2 + 2
    （其中 +2 表示新增 "ch" 和 "chch"）
  - 如果 left == right：中间只有一个 ch，新增的子序列是 ch 和 chch，但 "ch" 可能已被计算过？
    实际需修正为：
    dp[i][j] = dp[i+1][j-1] * 2 + 1
    （+1 表示新增 "chch"，而 "ch" 已在中间部分统计过）
  - 如果 left < right：中间有多个 ch，需减去 s[left+1..right-1] 中已统计过的重复子序列。
    转移方程：
    dp[i][j] = dp[i+1][j-1] * 2 - dp[left+1][right-1]
初始化
单个字符的子串 s[i..i] 只有一个回文子序列（即字符本身）：
dp[i][i] = 1
空子串（i > j）视为 0。
遍历顺序
按子串长度从小到大计算，外层循环遍历长度 len，内层循环遍历起始位置 i。
模运算
由于结果可能很大，每次更新 dp[i][j] 后取模 10^9+7。

示例计算（s = "bccb"）

初始化：所有 dp[i][i] = 1（如 dp[0][0]=1 表示 "b"）。
长度 2：
- "bc"：dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2（"b", "c"）
- "cc"：两端相同，中间无相同字符，dp[1][2] = 1*2 + 2 = 4（实际是 "c", "cc"，但需去重？这里需修正：实际不同子序列只有 "c" 和 "cc"，但 "c" 已统计过，因此 +1 即可，最终为 2）。
逐步计算至整个字符串，最终 dp[0][3] = 6。

关键点

去重核心：当两端字符相同时，通过查找中间相同字符的位置，避免重复计数。
时间复杂度 O(n²)，空间复杂度 O(n²)。

最长回文子序列的变种：统计不同非空回文子序列的个数题目描述给定一个字符串 s ，要求统计其中所有不同的非空回文子序列的个数。注意，这里的子序列是指从原字符串中删除零个或多个字符后，剩余字符相对位置不变形成的序列。由于不同位置的相同字符序列被视为同一个子序列，因此需要去重。结果可能很大，需要对 10^9 + 7 取模。例如，对于字符串 s = "bccb" ，不同的非空回文子序列有： "b" , "c" , "bb" , "cc" , "bcb" , "bccb" ，共 6 个。解题思路这是一个线性动态规划问题，关键在于如何避免重复计数。我们可以使用区间动态规划，定义 dp[i][j] 为字符串 s[i..j] 中不同回文子序列的个数。但直接统计会重复计算相同字符组成的子序列。因此，需要记录每个字符首次和最后一次出现的位置，确保在统计时每个字符组合只被计算一次。详细步骤定义状态设 dp[i][j] 表示子串 s[i..j] 中不同回文子序列的个数。目标是求 dp[0][n-1] ，其中 n 是字符串长度。状态转移考虑子串 s[i..j] ：如果 s[i] != s[j] ：回文子序列要么包含 s[i] 但不包含 s[j] ，要么包含 s[j] 但不包含 s[i] ，要么两者都不包含。但直接使用 dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] 会减去中间部分两次，需要加回。转移方程： dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] 如果 s[i] == s[j] （设字符为 ch ）：此时，所有 s[i+1..j-1] 中的回文子序列，两端加上 ch 后仍是回文子序列。此外，还需考虑单独由 ch 组成的子序列（如 "ch" 或 "chch" ）。但需避免重复：如果在 s[i+1..j-1] 中存在同样以 ch 开头和结尾的子序列，可能会重复计算。解决方法是找到子串 s[i+1..j-1] 中第一个等于 ch 的位置 left 和最后一个等于 ch 的位置 right ：如果 left > right ：说明中间没有字符 ch ，新增的子序列是 ch 和 chch 。转移方程： dp[i][j] = dp[i+1][j-1] * 2 + 2 （其中 +2 表示新增 "ch" 和 "chch" ）如果 left == right ：中间只有一个 ch ，新增的子序列是 ch 和 chch ，但 "ch" 可能已被计算过？实际需修正为： dp[i][j] = dp[i+1][j-1] * 2 + 1 （ +1 表示新增 "chch" ，而 "ch" 已在中间部分统计过）如果 left < right ：中间有多个 ch ，需减去 s[left+1..right-1] 中已统计过的重复子序列。转移方程： dp[i][j] = dp[i+1][j-1] * 2 - dp[left+1][right-1] 初始化单个字符的子串 s[i..i] 只有一个回文子序列（即字符本身）： dp[i][i] = 1 空子串（ i > j ）视为 0。遍历顺序按子串长度从小到大计算，外层循环遍历长度 len ，内层循环遍历起始位置 i 。模运算由于结果可能很大，每次更新 dp[i][j] 后取模 10^9+7 。示例计算（s = "bccb"）初始化：所有 dp[i][i] = 1 （如 dp[0][0]=1 表示 "b" ）。长度 2： "bc" ： dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2 （ "b" , "c" ） "cc" ：两端相同，中间无相同字符， dp[1][2] = 1*2 + 2 = 4 （实际是 "c" , "cc" ，但需去重？这里需修正：实际不同子序列只有 "c" 和 "cc" ，但 "c" 已统计过，因此 +1 即可，最终为 2）。逐步计算至整个字符串，最终 dp[0][3] = 6 。关键点去重核心：当两端字符相同时，通过查找中间相同字符的位置，避免重复计数。时间复杂度 O(n²)，空间复杂度 O(n²)。