最长回文子序列的变种：回文子序列的个数（不同长度统计）
字数 8521 2025-12-12 23:03:18

最长回文子序列的变种：回文子序列的个数（不同长度统计）

题目描述：
给定一个字符串 s，计算其所有回文子序列的个数，但需要分别统计每个可能长度（从 1 到 |s|）的回文子序列有多少个。子序列是从原字符串中删除一些（或不删除）字符，但不改变剩余字符的相对顺序得到的序列。两个子序列即使包含的字符相同，只要选取的下标位置不同，就视为不同的子序列。结果可能很大，通常需要对一个给定的大质数（如 10^9+7）取模。

解题过程：

步骤 1：明确子问题与状态定义
我们需要统计所有不同长度的回文子序列个数。这是一个动态规划问题，关键在于如何通过子问题的解来构造当前问题的解。
定义状态：
设 dp[i][j] 表示在子串 s[i..j]（包含 i 和 j）中，回文子序列的个数。但这样定义会包含很多重复计算，而且不容易直接统计不同长度。
更巧妙的定义是：
设 f[i][j] 表示在子串 s[i..j] 中，所有回文子序列的个数（不论长度），但这仍然没有区分长度。

为了统计每个长度的个数，我们可以增加一个维度 k 表示长度，但这样空间和时间会达到 O(n^3)，对稍大的 n 不可行。
另一种思路：我们仍然用二维动态规划，但状态表示子串 s[i..j] 中回文子序列的个数，然后通过递推关系自然地得到不同长度的统计。但最终需要输出每个长度对应的个数，所以我们需要在递推过程中累积不同长度的计数。

实际上，我们可以用另一种经典的回文子序列计数方法，然后对长度进行分解。
经典定义：
设 g[i][j] 表示子串 s[i..j] 中回文子序列的个数。
但 g[i][j] 会包含很多子序列，且会重复计算（因为不同子串可能共享相同的回文子序列）。
为了避免重复，我们通常定义：
dp[i][j] 表示在子串 s[i..j] 中，以 i 为开头、j 为结尾的回文子序列的个数。但这会限制开头和结尾必须是指定位置，不便于统计所有。

更标准的做法是定义：
dp[i][j] 表示子串 s[i..j] 中所有回文子序列的个数（包括空序列，但通常我们不计空序列）。
然后，转移方程如下：
如果 s[i] != s[j]：
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
（因为回文子序列要么完全在 s[i+1..j] 中，要么完全在 s[i..j-1] 中，但两者重叠部分在 s[i+1..j-1] 中被减掉）
如果 s[i] == s[j]：
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + (dp[i+1][j-1] + 1)
= dp[i+1][j] + dp[i][j-1] + 1
解释：当两端字符相等时，除了上述两种情况外，还可以用 s[i] 和 s[j] 作为新的开头和结尾，与 s[i+1..j-1] 中的所有回文子序列组合（每个子序列在两端加上 s[i] 和 s[j] 后仍然是回文），以及单独用 s[i]s[j] 作为一个长度为 2 的子序列。注意 dp[i+1][j-1] 是 s[i+1..j-1] 中的所有回文子序列个数，包括空序列（这里我们需要仔细处理空序列）。

为了避免重复计数，更严谨的定义是：
设 dp[i][j] 表示子串 s[i..j] 中所有回文子序列的个数（不包括空序列）。
则递推为：
如果 s[i] == s[j]：
dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1
（这里 dp[i+1][j] 包含了左端不用 i 但右端可能用 j 的子序列，dp[i][j-1] 包含了右端不用 j 但左端可能用 i 的子序列，而 1 是表示单独的子序列 s[i]s[j] ？不对，s[i]s[j] 是长度为 2 的序列，但 s[i] 和 s[j] 各自单独作为长度为 1 的子序列已经被包含在子问题中。实际上，s[i] 和 s[j] 作为长度为 1 的子序列会通过更小的区间被统计。当 s[i]==s[j] 时，我们需要加上所有用 s[i] 和 s[j] 作为两端的回文子序列，即 dp[i+1][j-1] 中的每个回文子序列在两端加上 s[i] 和 s[j] 后形成的新子序列，以及 s[i]s[j] 这个长度为 2 的子序列。而 dp[i+1][j-1] 中的回文子序列个数（不包括空序列）加上空序列（1 个）就对应了所有可以两端添加的组合。但注意，dp[i+1][j-1] 中已经统计了所有回文子序列，当我们用两端包裹时，每个都会产生一个新的、长度增加 2 的子序列。另外，单独 s[i]s[j] 可以看作是用空序列包裹得到的。所以，新产生的子序列个数正好是 dp[i+1][j-1] + 1。
因此，转移方程为：
当 s[i]==s[j] 时，
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + (dp[i+1][j-1] + 1)
= dp[i+1][j] + dp[i][j-1] + 1
当 s[i]!=s[j] 时，
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

然而，这个 dp 统计的是所有长度的回文子序列总数，但我们希望按长度分别统计。
因此，我们需要另一个状态数组 cnt[len][i][j] 表示在子串 s[i..j] 中，长度为 len 的回文子序列个数。但这样是 O(n^3) 时间和空间，当 n 较大时不可行。

我们需要一个更高效的方法。注意到，我们可以用区间 DP 来统计所有回文子序列，并同时记录长度信息。
定义 f[i][j] 表示子串 s[i..j] 中所有回文子序列的个数（同上面 dp），同时，我们需要一个辅助数组 lenCount[l] 来统计整个字符串中长度为 l 的回文子序列个数。
那么，在计算 f[i][j] 时，我们知道新增的子序列的长度与从子问题中产生的子序列长度有关。
具体来说，当 s[i]==s[j] 时，从 dp[i+1][j-1] 中每一个回文子序列，在两端加上 s[i] 和 s[j] 后，长度增加了 2。另外，还新增了一个长度为 2 的子序列 s[i]s[j]。
所以，我们可以维护一个数组 cnt[i][j][l] 表示在子串 s[i..j] 中长度为 l 的回文子序列个数。但这仍然是三维。
观察发现，长度 l 只与区间长度 (j-i+1) 有关，而且转移时长度要么不变（从 dp[i+1][j] 或 dp[i][j-1]），要么增加 2（当两端相等时）。因此，我们可以用区间长度作为阶段，从小到大地计算。

步骤 2：新的状态定义
设 dp[l][i] 表示以 i 开头、长度为 l 的回文子序列的个数，但这样难以转移。
一个经典的技巧是：定义 f[i][j] 为子串 s[i..j] 中回文子序列的个数，并同时用另一个数组 g[len][i][j] 来记录长度为 len 的个数，但我们可以通过 f 的递推来得到每个长度的贡献。

实际上，我们可以这样考虑：
定义 f[i][j] 为子串 s[i..j] 中回文子序列的个数（同前），并额外记录一个贡献数组 add[i][j] 表示在计算 f[i][j] 时，新产生的回文子序列（即那些必须包含 s[i] 和 s[j] 作为两端的子序列）的个数。当 s[i]==s[j] 时，add[i][j] = f[i+1][j-1] + 1（这个 1 对应 s[i]s[j] 这个长度为 2 的序列）。这些新产生的子序列的长度，等于在 s[i+1..j-1] 中的每个回文子序列的长度加 2，再加上长度为 2 的那个。
那么，如果我们能够知道 f[i+1][j-1] 中每个长度的回文子序列个数，我们就可以相应地更新总长度统计。

所以，我们可以维护一个二维数组 cnt[len][i][j] 吗？空间太大。
注意到，在动态规划过程中，我们按区间长度从小到大计算。当我们计算区间 [i,j] 时，区间 [i+1,j-1] 的长度更小，已经被计算过。我们可以用一个全局数组 totalLen[l] 来记录整个字符串中长度为 l 的回文子序列个数。在计算每个区间 [i,j] 时，如果 s[i]==s[j]，那么 add[i][j] 中包含的所有新子序列，它们的长度分布可以从 cnt'[len-2][i+1][j-1] 得到。但 cnt' 是三维的，我们需要优化。

我们可以改变思路：直接定义 dpLen[i][j][l] 为在子串 s[i..j] 中，回文子序列的长度为 l 的个数。转移方程为：
如果 s[i] != s[j]：
dpLen[i][j][l] = dpLen[i+1][j][l] + dpLen[i][j-1][l] - dpLen[i+1][j-1][l]
如果 s[i] == s[j]：
dpLen[i][j][l] = dpLen[i+1][j][l] + dpLen[i][j-1][l] - dpLen[i+1][j-1][l] + (l>=2 ? dpLen[i+1][j-1][l-2] : 0) + (l==2 ? 1 : 0)
其中，dpLen[i+1][j-1][l-2] 表示用 s[i] 和 s[j] 包裹长度为 l-2 的子序列得到长度为 l 的子序列，而 (l==2 ? 1 : 0) 对应单独的子序列 s[i]s[j]。
这样，我们可以从小区间递推到大区间。
初始化：对于每个位置 i，dpLen[i][i][1] = 1（单个字符是回文）。
最终，整个字符串的每个长度 l 的个数为 dpLen[0][n-1][l]。
这个算法时间复杂度为 O(n^3)，因为有三层循环：区间长度、起点、长度 l。当 n 较大时，可能需要优化。但题目通常 n 不超过 500，O(n^3) 是可以接受的（500^3=1.25亿，可能稍大，但实际中很多状态是无效的，因为 l 不能超过区间长度）。

步骤 3：优化空间
我们可以将 dpLen 的第三维压缩，因为 l 只依赖于更小的 l-2，而且区间长度递增计算时，我们可以只保存当前区间所需的状态。但为了清晰，我们可以保留三维，但注意 l 的范围是 1 到区间长度。
我们可以用滚动数组在 l 维度上优化吗？不简单，因为转移中需要 dpLen[i+1][j-1][l-2]，这是上一阶段小区间的状态。
另一种优化：因为 l 只与区间长度有关，我们可以按区间长度从小到大枚举，然后对每个区间 [i,j]，计算所有可能的 l。
实现时，用三维数组 dp[i][j][l] 会占用 O(n^3) 空间，如果 n=500，需要 500500500=125M 个整数，可能内存过大。我们可以用二维数组 dp[i][j] 存储一个列表或字典，记录该区间内每个长度的个数，但这样时间可能增加。
鉴于题目要求统计每个长度的个数，且 n 可能较大，我们需要更高效的算法。
实际上，有一个经典的回文子序列计数问题，其状态定义为 f[i][j] 表示子串 s[i..j] 中回文子序列的个数，然后通过容斥转移。要得到长度分布，可以在该递推中同时更新一个全局的长度统计数组。
具体做法：
设 f[i][j] 为子串 s[i..j] 中回文子序列的个数。
转移：
如果 s[i] != s[j]: f[i][j] = f[i+1][j] + f[i][j-1] - f[i+1][j-1]
如果 s[i] == s[j]: f[i][j] = f[i+1][j] + f[i][j-1] + 1
注意，当 s[i]==s[j] 时，新增的子序列包括：所有用 s[i] 和 s[j] 包裹 f[i+1][j-1] 中的子序列（每个子序列长度+2），以及 s[i]s[j] 这个长度为 2 的子序列。
那么，如果我们有一个数组 totalLen[l] 表示整个字符串中长度为 l 的回文子序列个数，我们可以在每次计算 f[i][j] 时，如果 s[i]==s[j]，我们就将 f[i+1][j-1] 中每个长度对应的子序列个数加到 totalLen[l+2] 上，并将 totalLen[2] 加 1。但 f[i+1][j-1] 中每个长度的个数我们并不知道。
所以，我们需要在计算 f 的同时，维护每个区间内各长度的分布。
我们可以用二维数组 lenDist[i][j] 来表示一个映射，键为长度 l，值为个数。但这样空间和时间会很大。

步骤 4：使用区间 DP 直接计算每个长度的个数
重新考虑三维 DP 定义：
dp[i][j][l] 表示在子串 s[i..j] 中，回文子序列的长度恰好为 l 的个数。
初始化：
对于每个 i，dp[i][i][1] = 1。
对于每个 i < j，如果 s[i]==s[j] 且 j==i+1，则 dp[i][j][2] = 1，同时 dp[i][j][1] = 2？不对，单个字符的子序列在子串 s[i..j] 中有两个：s[i] 和 s[j]。但注意，在更大的区间中，单个字符的子序列会通过转移被包含。
我们通过递推计算：
对于区间 [i,j]，长度 len = j-i+1。
转移分两种情况：

  1. 回文子序列不包含 s[i] 和 s[j]：贡献为 dp[i+1][j-1][l]
  2. 包含 s[i] 但不包含 s[j]：贡献为 dp[i][j-1][l] - dp[i+1][j-1][l]（实际上，这是不包含 s[j] 但可能包含 s[i] 的子序列，减去两者都不包含的）
  3. 包含 s[j] 但不包含 s[i]：贡献为 dp[i+1][j][l] - dp[i+1][j-1][l]
  4. 同时包含 s[i] 和 s[j]：这要求 s[i]==s[j]，此时子序列由 s[i] 和 s[j] 包裹一个内部回文子序列构成，所以贡献为：如果 l>=2 且 s[i]==s[j]，则加上 dp[i+1][j-1][l-2]；另外，当 l==2 时，还有单独的子序列 s[i]s[j]，所以再加 1。

综合上述，总转移方程为：
dp[i][j][l] = dp[i+1][j][l] + dp[i][j-1][l] - dp[i+1][j-1][l] + (s[i]==s[j] ? (l>=2 ? dp[i+1][j-1][l-2] : 0) + (l==2 ? 1 : 0) : 0)
但要注意，当区间长度为 1 时，l 只能为 1，我们已经初始化。
这个方程中，dp[i+1][j][l] 和 dp[i][j-1][l] 包含了情况 1,2,3，减去 dp[i+1][j-1][l] 是为了扣除重复计算的情况 1。然后加上情况 4 的贡献。

步骤 5：计算顺序与最终统计
我们按区间长度从小到大枚举。
对于每个区间 [i,j]，枚举可能的子序列长度 l（从 1 到区间长度）。
最终，对于整个字符串，totalLen[l] = dp[0][n-1][l]。
复杂度：O(n^3)。对于 n=500，大约 1.25 亿次操作，在合理优化下可以在 1 秒左右完成。

步骤 6：边界处理与取模
所有计算需要对大质数取模，避免溢出。
初始化 dp[i][i][1] = 1，其他为 0。
当区间长度为 2 时，例如 s[i] 和 s[j]，
如果 s[i]==s[j]，则 dp[i][j][2] = 1，dp[i][j][1] = 2。
如果 s[i]!=s[j]，则 dp[i][j][1] = 2，dp[i][j][2] = 0。
注意，长度为 1 的子序列总是存在的，个数等于区间内的字符数。但我们的递推会自动计算出这些值吗？
检验一下递推公式：
当区间长度为 2，i=0, j=1，l=1 时，
dp[0][1][1] = dp[1][1][1] + dp[0][0][1] - dp[1][0][1] + ...
dp[1][0] 是无效区间，我们定义无效区间的 dp 值为 0。
则 dp[0][1][1] = 1+1-0 =2，正确。
当 l=2 时，如果 s[0]==s[1]，
dp[0][1][2] = dp[1][1][2] + dp[0][0][2] - dp[1][0][2] + (dp[1][0][0] + 1)
无效区间 dp 值为 0，dp[1][1][2] 和 dp[0][0][2] 均为 0，dp[1][0][0] 我们定义为 1（空序列的个数），但这里 dp[i+1][j-1][l-2] 当 l=2 时为 dp[1][0][0]，我们通常不将空序列计入 dp 中，所以 dp[1][0][0] 应为 0。但这样会缺少 s[0]s[1] 这个序列。
所以，我们需要特别处理空序列。通常，我们定义 dp[i][j][0] = 1（空序列），但这样会增加维度。
为了避免混乱，我们可以将情况 4 中的“内部子序列”包括空序列。即，当 s[i]==s[j] 时，新子序列包括：用 s[i] 和 s[j] 包裹内部任意回文子序列（包括空序列），所以新增个数为 (dp[i+1][j-1] 的所有回文子序列个数)，即 f[i+1][j-1] + 1（其中 +1 是空序列）。而 f[i+1][j-1] 本身是内部回文子序列总数（不包括空序列）。
所以，如果我们用 dpLen 统计长度分布，则当 s[i]==s[j] 时，对于每个长度 l，新增的个数为 dpLen[i+1][j-1][l]（当 l>=2 时，对应内部长度为 l-2 的子序列）加上 (l==2 ? 1 : 0)（对应内部空序列产生的长度为 2 的子序列）。但 dpLen[i+1][j-1][l] 中不包括空序列，所以我们需要单独处理空序列产生的长度为 2 的子序列。
因此，转移方程修正为：
dp[i][j][l] = dp[i+1][j][l] + dp[i][j-1][l] - dp[i+1][j-1][l] + (s[i]==s[j] ? (l>=2 ? dp[i+1][j-1][l-2] : 0) + (l==2 ? 1 : 0) : 0)
其中，当 i>j 时，区间无效，dp 值为 0。但当 i+1 > j-1 时，即区间长度为 0 或负，我们定义 dp[i+1][j-1][*] = 0，除了当 l=2 时，我们手动加 1 来对应空序列产生的子序列。

步骤 7：实现细节
我们将 dp 实现为三维数组，但可以只存储必要的区间。
枚举顺序：先枚举区间长度 len 从 1 到 n，然后枚举起点 i，计算 j = i+len-1。
对于每个区间 [i,j]，枚举子序列长度 l 从 1 到 len。
用公式计算 dp[i][j][l]，注意取模。
初始化：对于每个 i，dp[i][i][1] = 1。
最终输出 dp[0][n-1][l] 对每个 l 从 1 到 n。

这个算法可以正确统计每个长度的回文子序列个数。虽然复杂度较高，但对于 n 不超过 200 左右是可行的。如果 n 更大，可能需要进一步优化，比如利用对称性减少状态，或者用分治等。但题目一般会给出适当的 n 范围。

最长回文子序列的变种：回文子序列的个数（不同长度统计） 题目描述： 给定一个字符串 s，计算其所有回文子序列的个数，但需要分别统计每个可能长度（从 1 到 |s|）的回文子序列有多少个。子序列是从原字符串中删除一些（或不删除）字符，但不改变剩余字符的相对顺序得到的序列。两个子序列即使包含的字符相同，只要选取的下标位置不同，就视为不同的子序列。结果可能很大，通常需要对一个给定的大质数（如 10^9+7）取模。 解题过程： 步骤 1：明确子问题与状态定义 我们需要统计所有不同长度的回文子序列个数。这是一个动态规划问题，关键在于如何通过子问题的解来构造当前问题的解。 定义状态： 设 dp[ i][ j] 表示在子串 s[ i..j ]（包含 i 和 j）中，回文子序列的个数。但这样定义会包含很多重复计算，而且不容易直接统计不同长度。 更巧妙的定义是： 设 f[ i][ j] 表示在子串 s[ i..j ] 中，所有回文子序列的个数（不论长度），但这仍然没有区分长度。 为了统计每个长度的个数，我们可以增加一个维度 k 表示长度，但这样空间和时间会达到 O(n^3)，对稍大的 n 不可行。 另一种思路：我们仍然用二维动态规划，但状态表示子串 s[ i..j ] 中回文子序列的个数，然后通过递推关系自然地得到不同长度的统计。但最终需要输出每个长度对应的个数，所以我们需要在递推过程中累积不同长度的计数。 实际上，我们可以用另一种经典的回文子序列计数方法，然后对长度进行分解。 经典定义： 设 g[ i][ j] 表示子串 s[ i..j ] 中回文子序列的个数。 但 g[ i][ j ] 会包含很多子序列，且会重复计算（因为不同子串可能共享相同的回文子序列）。 为了避免重复，我们通常定义： dp[ i][ j] 表示在子串 s[ i..j ] 中，以 i 为开头、j 为结尾的回文子序列的个数。但这会限制开头和结尾必须是指定位置，不便于统计所有。 更标准的做法是定义： dp[ i][ j] 表示子串 s[ i..j ] 中所有回文子序列的个数（包括空序列，但通常我们不计空序列）。 然后，转移方程如下： 如果 s[ i] != s[ j ]： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] （因为回文子序列要么完全在 s[ i+1..j] 中，要么完全在 s[ i..j-1] 中，但两者重叠部分在 s[ i+1..j-1 ] 中被减掉） 如果 s[ i] == s[ j ]： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1] + (dp[ i+1][ j-1 ] + 1) = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 解释：当两端字符相等时，除了上述两种情况外，还可以用 s[ i] 和 s[ j] 作为新的开头和结尾，与 s[ i+1..j-1] 中的所有回文子序列组合（每个子序列在两端加上 s[ i] 和 s[ j] 后仍然是回文），以及单独用 s[ i]s[ j] 作为一个长度为 2 的子序列。注意 dp[ i+1][ j-1] 是 s[ i+1..j-1 ] 中的所有回文子序列个数，包括空序列（这里我们需要仔细处理空序列）。 为了避免重复计数，更严谨的定义是： 设 dp[ i][ j] 表示子串 s[ i..j ] 中所有回文子序列的个数（不包括空序列）。 则递推为： 如果 s[ i] == s[ j ]： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 （这里 dp[ i+1][ j] 包含了左端不用 i 但右端可能用 j 的子序列，dp[ i][ j-1] 包含了右端不用 j 但左端可能用 i 的子序列，而 1 是表示单独的子序列 s[ i]s[ j] ？不对，s[ i]s[ j] 是长度为 2 的序列，但 s[ i] 和 s[ j] 各自单独作为长度为 1 的子序列已经被包含在子问题中。实际上，s[ i] 和 s[ j] 作为长度为 1 的子序列会通过更小的区间被统计。当 s[ i]==s[ j] 时，我们需要加上所有用 s[ i] 和 s[ j] 作为两端的回文子序列，即 dp[ i+1][ j-1] 中的每个回文子序列在两端加上 s[ i] 和 s[ j] 后形成的新子序列，以及 s[ i]s[ j] 这个长度为 2 的子序列。而 dp[ i+1][ j-1] 中的回文子序列个数（不包括空序列）加上空序列（1 个）就对应了所有可以两端添加的组合。但注意，dp[ i+1][ j-1] 中已经统计了所有回文子序列，当我们用两端包裹时，每个都会产生一个新的、长度增加 2 的子序列。另外，单独 s[ i]s[ j] 可以看作是用空序列包裹得到的。所以，新产生的子序列个数正好是 dp[ i+1][ j-1 ] + 1。 因此，转移方程为： 当 s[ i]==s[ j ] 时， dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1] + (dp[ i+1][ j-1 ] + 1) = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 当 s[ i]!=s[ j ] 时， dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] 然而，这个 dp 统计的是所有长度的回文子序列总数，但我们希望按长度分别统计。 因此，我们需要另一个状态数组 cnt[ len][ i][ j] 表示在子串 s[ i..j ] 中，长度为 len 的回文子序列个数。但这样是 O(n^3) 时间和空间，当 n 较大时不可行。 我们需要一个更高效的方法。注意到，我们可以用区间 DP 来统计所有回文子序列，并同时记录长度信息。 定义 f[ i][ j] 表示子串 s[ i..j] 中所有回文子序列的个数（同上面 dp），同时，我们需要一个辅助数组 lenCount[ l ] 来统计整个字符串中长度为 l 的回文子序列个数。 那么，在计算 f[ i][ j ] 时，我们知道新增的子序列的长度与从子问题中产生的子序列长度有关。 具体来说，当 s[ i]==s[ j] 时，从 dp[ i+1][ j-1] 中每一个回文子序列，在两端加上 s[ i] 和 s[ j] 后，长度增加了 2。另外，还新增了一个长度为 2 的子序列 s[ i]s[ j ]。 所以，我们可以维护一个数组 cnt[ i][ j][ l] 表示在子串 s[ i..j ] 中长度为 l 的回文子序列个数。但这仍然是三维。 观察发现，长度 l 只与区间长度 (j-i+1) 有关，而且转移时长度要么不变（从 dp[ i+1][ j] 或 dp[ i][ j-1 ]），要么增加 2（当两端相等时）。因此，我们可以用区间长度作为阶段，从小到大地计算。 步骤 2：新的状态定义 设 dp[ l][ i ] 表示以 i 开头、长度为 l 的回文子序列的个数，但这样难以转移。 一个经典的技巧是：定义 f[ i][ j] 为子串 s[ i..j] 中回文子序列的个数，并同时用另一个数组 g[ len][ i][ j ] 来记录长度为 len 的个数，但我们可以通过 f 的递推来得到每个长度的贡献。 实际上，我们可以这样考虑： 定义 f[ i][ j] 为子串 s[ i..j] 中回文子序列的个数（同前），并额外记录一个贡献数组 add[ i][ j] 表示在计算 f[ i][ j] 时，新产生的回文子序列（即那些必须包含 s[ i] 和 s[ j] 作为两端的子序列）的个数。当 s[ i]==s[ j] 时，add[ i][ j] = f[ i+1][ j-1] + 1（这个 1 对应 s[ i]s[ j] 这个长度为 2 的序列）。这些新产生的子序列的长度，等于在 s[ i+1..j-1 ] 中的每个回文子序列的长度加 2，再加上长度为 2 的那个。 那么，如果我们能够知道 f[ i+1][ j-1 ] 中每个长度的回文子序列个数，我们就可以相应地更新总长度统计。 所以，我们可以维护一个二维数组 cnt[ len][ i][ j ] 吗？空间太大。 注意到，在动态规划过程中，我们按区间长度从小到大计算。当我们计算区间 [ i,j] 时，区间 [ i+1,j-1] 的长度更小，已经被计算过。我们可以用一个全局数组 totalLen[ l] 来记录整个字符串中长度为 l 的回文子序列个数。在计算每个区间 [ i,j] 时，如果 s[ i]==s[ j]，那么 add[ i][ j] 中包含的所有新子序列，它们的长度分布可以从 cnt'[ len-2][ i+1][ j-1 ] 得到。但 cnt' 是三维的，我们需要优化。 我们可以改变思路：直接定义 dpLen[ i][ j][ l] 为在子串 s[ i..j ] 中，回文子序列的长度为 l 的个数。转移方程为： 如果 s[ i] != s[ j ]： dpLen[ i][ j][ l] = dpLen[ i+1][ j][ l] + dpLen[ i][ j-1][ l] - dpLen[ i+1][ j-1][ l ] 如果 s[ i] == s[ j ]： dpLen[ i][ j][ l] = dpLen[ i+1][ j][ l] + dpLen[ i][ j-1][ l] - dpLen[ i+1][ j-1][ l] + (l>=2 ? dpLen[ i+1][ j-1][ l-2 ] : 0) + (l==2 ? 1 : 0) 其中，dpLen[ i+1][ j-1][ l-2] 表示用 s[ i] 和 s[ j] 包裹长度为 l-2 的子序列得到长度为 l 的子序列，而 (l==2 ? 1 : 0) 对应单独的子序列 s[ i]s[ j ]。 这样，我们可以从小区间递推到大区间。 初始化：对于每个位置 i，dpLen[ i][ i][ 1 ] = 1（单个字符是回文）。 最终，整个字符串的每个长度 l 的个数为 dpLen[ 0][ n-1][ l ]。 这个算法时间复杂度为 O(n^3)，因为有三层循环：区间长度、起点、长度 l。当 n 较大时，可能需要优化。但题目通常 n 不超过 500，O(n^3) 是可以接受的（500^3=1.25亿，可能稍大，但实际中很多状态是无效的，因为 l 不能超过区间长度）。 步骤 3：优化空间 我们可以将 dpLen 的第三维压缩，因为 l 只依赖于更小的 l-2，而且区间长度递增计算时，我们可以只保存当前区间所需的状态。但为了清晰，我们可以保留三维，但注意 l 的范围是 1 到区间长度。 我们可以用滚动数组在 l 维度上优化吗？不简单，因为转移中需要 dpLen[ i+1][ j-1][ l-2 ]，这是上一阶段小区间的状态。 另一种优化：因为 l 只与区间长度有关，我们可以按区间长度从小到大枚举，然后对每个区间 [ i,j ]，计算所有可能的 l。 实现时，用三维数组 dp[ i][ j][ l] 会占用 O(n^3) 空间，如果 n=500，需要 500 500 500=125M 个整数，可能内存过大。我们可以用二维数组 dp[ i][ j ] 存储一个列表或字典，记录该区间内每个长度的个数，但这样时间可能增加。 鉴于题目要求统计每个长度的个数，且 n 可能较大，我们需要更高效的算法。 实际上，有一个经典的回文子序列计数问题，其状态定义为 f[ i][ j] 表示子串 s[ i..j ] 中回文子序列的个数，然后通过容斥转移。要得到长度分布，可以在该递推中同时更新一个全局的长度统计数组。 具体做法： 设 f[ i][ j] 为子串 s[ i..j ] 中回文子序列的个数。 转移： 如果 s[ i] != s[ j]: f[ i][ j] = f[ i+1][ j] + f[ i][ j-1] - f[ i+1][ j-1 ] 如果 s[ i] == s[ j]: f[ i][ j] = f[ i+1][ j] + f[ i][ j-1 ] + 1 注意，当 s[ i]==s[ j] 时，新增的子序列包括：所有用 s[ i] 和 s[ j] 包裹 f[ i+1][ j-1] 中的子序列（每个子序列长度+2），以及 s[ i]s[ j ] 这个长度为 2 的子序列。 那么，如果我们有一个数组 totalLen[ l] 表示整个字符串中长度为 l 的回文子序列个数，我们可以在每次计算 f[ i][ j] 时，如果 s[ i]==s[ j]，我们就将 f[ i+1][ j-1] 中每个长度对应的子序列个数加到 totalLen[ l+2] 上，并将 totalLen[ 2] 加 1。但 f[ i+1][ j-1 ] 中每个长度的个数我们并不知道。 所以，我们需要在计算 f 的同时，维护每个区间内各长度的分布。 我们可以用二维数组 lenDist[ i][ j ] 来表示一个映射，键为长度 l，值为个数。但这样空间和时间会很大。 步骤 4：使用区间 DP 直接计算每个长度的个数 重新考虑三维 DP 定义： dp[ i][ j][ l] 表示在子串 s[ i..j ] 中，回文子序列的长度恰好为 l 的个数。 初始化： 对于每个 i，dp[ i][ i][ 1 ] = 1。 对于每个 i < j，如果 s[ i]==s[ j] 且 j==i+1，则 dp[ i][ j][ 2] = 1，同时 dp[ i][ j][ 1] = 2？不对，单个字符的子序列在子串 s[ i..j] 中有两个：s[ i] 和 s[ j ]。但注意，在更大的区间中，单个字符的子序列会通过转移被包含。 我们通过递推计算： 对于区间 [ i,j ]，长度 len = j-i+1。 转移分两种情况： 回文子序列不包含 s[ i] 和 s[ j]：贡献为 dp[ i+1][ j-1][ l ] 包含 s[ i] 但不包含 s[ j]：贡献为 dp[ i][ j-1][ l] - dp[ i+1][ j-1][ l]（实际上，这是不包含 s[ j] 但可能包含 s[ i ] 的子序列，减去两者都不包含的） 包含 s[ j] 但不包含 s[ i]：贡献为 dp[ i+1][ j][ l] - dp[ i+1][ j-1][ l ] 同时包含 s[ i] 和 s[ j]：这要求 s[ i]==s[ j]，此时子序列由 s[ i] 和 s[ j] 包裹一个内部回文子序列构成，所以贡献为：如果 l>=2 且 s[ i]==s[ j]，则加上 dp[ i+1][ j-1][ l-2]；另外，当 l==2 时，还有单独的子序列 s[ i]s[ j ]，所以再加 1。 综合上述，总转移方程为： dp[ i][ j][ l] = dp[ i+1][ j][ l] + dp[ i][ j-1][ l] - dp[ i+1][ j-1][ l] + (s[ i]==s[ j] ? (l>=2 ? dp[ i+1][ j-1][ l-2 ] : 0) + (l==2 ? 1 : 0) : 0) 但要注意，当区间长度为 1 时，l 只能为 1，我们已经初始化。 这个方程中，dp[ i+1][ j][ l] 和 dp[ i][ j-1][ l] 包含了情况 1,2,3，减去 dp[ i+1][ j-1][ l ] 是为了扣除重复计算的情况 1。然后加上情况 4 的贡献。 步骤 5：计算顺序与最终统计 我们按区间长度从小到大枚举。 对于每个区间 [ i,j ]，枚举可能的子序列长度 l（从 1 到区间长度）。 最终，对于整个字符串，totalLen[ l] = dp[ 0][ n-1][ l ]。 复杂度：O(n^3)。对于 n=500，大约 1.25 亿次操作，在合理优化下可以在 1 秒左右完成。 步骤 6：边界处理与取模 所有计算需要对大质数取模，避免溢出。 初始化 dp[ i][ i][ 1 ] = 1，其他为 0。 当区间长度为 2 时，例如 s[ i] 和 s[ j ]， 如果 s[ i]==s[ j]，则 dp[ i][ j][ 2] = 1，dp[ i][ j][ 1 ] = 2。 如果 s[ i]!=s[ j]，则 dp[ i][ j][ 1] = 2，dp[ i][ j][ 2 ] = 0。 注意，长度为 1 的子序列总是存在的，个数等于区间内的字符数。但我们的递推会自动计算出这些值吗？ 检验一下递推公式： 当区间长度为 2，i=0, j=1，l=1 时， dp[ 0][ 1][ 1] = dp[ 1][ 1][ 1] + dp[ 0][ 0][ 1] - dp[ 1][ 0][ 1 ] + ... dp[ 1][ 0 ] 是无效区间，我们定义无效区间的 dp 值为 0。 则 dp[ 0][ 1][ 1 ] = 1+1-0 =2，正确。 当 l=2 时，如果 s[ 0]==s[ 1 ]， dp[ 0][ 1][ 2] = dp[ 1][ 1][ 2] + dp[ 0][ 0][ 2] - dp[ 1][ 0][ 2] + (dp[ 1][ 0][ 0 ] + 1) 无效区间 dp 值为 0，dp[ 1][ 1][ 2] 和 dp[ 0][ 0][ 2] 均为 0，dp[ 1][ 0][ 0] 我们定义为 1（空序列的个数），但这里 dp[ i+1][ j-1][ l-2] 当 l=2 时为 dp[ 1][ 0][ 0]，我们通常不将空序列计入 dp 中，所以 dp[ 1][ 0][ 0] 应为 0。但这样会缺少 s[ 0]s[ 1 ] 这个序列。 所以，我们需要特别处理空序列。通常，我们定义 dp[ i][ j][ 0 ] = 1（空序列），但这样会增加维度。 为了避免混乱，我们可以将情况 4 中的“内部子序列”包括空序列。即，当 s[ i]==s[ j] 时，新子序列包括：用 s[ i] 和 s[ j] 包裹内部任意回文子序列（包括空序列），所以新增个数为 (dp[ i+1][ j-1] 的所有回文子序列个数)，即 f[ i+1][ j-1] + 1（其中 +1 是空序列）。而 f[ i+1][ j-1 ] 本身是内部回文子序列总数（不包括空序列）。 所以，如果我们用 dpLen 统计长度分布，则当 s[ i]==s[ j] 时，对于每个长度 l，新增的个数为 dpLen[ i+1][ j-1][ l]（当 l>=2 时，对应内部长度为 l-2 的子序列）加上 (l==2 ? 1 : 0)（对应内部空序列产生的长度为 2 的子序列）。但 dpLen[ i+1][ j-1][ l ] 中不包括空序列，所以我们需要单独处理空序列产生的长度为 2 的子序列。 因此，转移方程修正为： dp[ i][ j][ l] = dp[ i+1][ j][ l] + dp[ i][ j-1][ l] - dp[ i+1][ j-1][ l] + (s[ i]==s[ j] ? (l>=2 ? dp[ i+1][ j-1][ l-2 ] : 0) + (l==2 ? 1 : 0) : 0) 其中，当 i>j 时，区间无效，dp 值为 0。但当 i+1 > j-1 时，即区间长度为 0 或负，我们定义 dp[ i+1][ j-1][* ] = 0，除了当 l=2 时，我们手动加 1 来对应空序列产生的子序列。 步骤 7：实现细节 我们将 dp 实现为三维数组，但可以只存储必要的区间。 枚举顺序：先枚举区间长度 len 从 1 到 n，然后枚举起点 i，计算 j = i+len-1。 对于每个区间 [ i,j ]，枚举子序列长度 l 从 1 到 len。 用公式计算 dp[ i][ j][ l ]，注意取模。 初始化：对于每个 i，dp[ i][ i][ 1 ] = 1。 最终输出 dp[ 0][ n-1][ l ] 对每个 l 从 1 到 n。 这个算法可以正确统计每个长度的回文子序列个数。虽然复杂度较高，但对于 n 不超过 200 左右是可行的。如果 n 更大，可能需要进一步优化，比如利用对称性减少状态，或者用分治等。但题目一般会给出适当的 n 范围。