字符串中回文子序列的总数

Question

问题是这样的--

对于作为输入给出的每个字符串，您需要告诉它的回文子序列的数量（不一定是不同的）。请注意，空字符串不是回文。例如"aab"的回文子序列为：

"a"、"a"、"b"、"aa"，方法returns 4.

我想到了寻找最长回文子序列的动态规划解决方案，因此尝试从中汲取灵感。无法真正得到解决方案。可能甚至不需要动态规划。请提出建议。

还有一个收获。当条件"need not necessarily be distinct"去掉后，我们是否还可以计数而不实际生成所有回文子序列？

Answer 1

这是一个可怕的 O(n^4) 解决方案：

每个回文子序列都从某个位置 i 开始并在某个位置 j >= i 结束，使得 x[i] = x[j] 及其 "interior"（除第一个和最后一个字符外的所有字符）为空或 x[i+1 .. j-1].

的回文子序列

所以我们可以定义f(i, j)为从i开始到j >= i结束的回文子序列的个数。那么

f(i, j) = 0 if x[i] != x[j]
f(i, i) = 1 (i.e. when j = i)
f(i, j) = 1 + the sum of f(i', j') over all i < i' <= j' < j otherwise

[编辑：固定计算长度 <= 2 的回文子序列！]

那么最后的答案就是 f(i, j) 在所有 1 <= i <= j <= n 上的总和。

这个的 DP 是 O(n^4) 因为有 n^2 table 个条目，计算每个条目需要 O(n^2) 时间。（利用 x[i] != x[j] 意味着 f(i, j) = 0 的事实，可能可以将其加速到至少 O(n^3)。）

Answer 2

[编辑 2015 年 10 月 19 日：一位匿名审阅者指出了公式的一个问题，这促使我注意到另一个更大的错误……现已修复。]

我现在知道如何将求解时间降低到 O(n^2)。我会留下我的另一个答案，以防它作为这个问题的垫脚石很有趣。注意：这（也）只是问题第一部分的解决方案；我认为没有办法有效地只计算 distinct 回文子序列 (PS).

与其计算恰好在位置 i 和 j 开始和结束的 PS 的数量，不如计算有多少开始于 或之后 i 并结束于或之前称之为 g(i, j).

我们可以试着写成g(i, j) = g(i, j-1) + g(i+1, j) + (x[i] == x[j])* g(i+1, j-1) 对于 j > i 的情况。但这并不完全有效，因为前两项将重复计算任何 PS 开始 after i 和结束 before j.

关键的洞察力是注意到我们可以通过减去 g( ), 并可能重新添加更多的 g() 值以补偿重复计算。例如，从 exactlyi 开始到 exactlyj 结束的 PS 的数量是 g(i, j) - g (i+1, j) - g(i, j-1) + g(i+1, j-1)：最后一项纠正了第二项和第三项都计算所有 g(i+1, j-1) PS 开始 after i 并结束 before j.

从 i 或之后开始并在 j 或之前结束的每个 PS 恰好属于 4 个类别中的 1 个：

从 i 开始，在 j 之前结束。
从 i 开始，到 j 之前结束。
从 i 开始，到 j 结束。
从 i 开始，到 j 结束。

g(i+1, j) 统计了类别 1 或类别 3 中的所有 PS，而 g(i, j-1) 统计了类别 1 或 2 中的所有 PS，因此它们的sum g(i+1, j) + g(i, j-1) 对类别 2 或 3 中的所有 PS 各计数一次，对类别 1 中的所有 PS 计数两次。由于 g(i+1, j-1) 只计算类别 1 中的所有 PS，因此减去它得到 g(i+1, j) + g(i, j-1) - g(i+ 1, j-1) 给出第1、2、3类的PS的总数，剩下的PS就是第4类的。如果x[i] != x[j]那么这个分类就没有PS；否则，从 i+1 或之后开始并在 j-1 或之前结束的 PS 恰好一样多，即 g(i+1, j-1)，再加上 2 -字符序列x[i]x[j]。 [编辑：感谢评论者 Tuxdude 在这里进行了 2 处修复！]

有了这个，我们可以用一种将二次情况从 f() 更改为常数时间的方式来表达 g()：

g(i, i) = 1 (i.e. when j = i)
g(i, i+1) = 2 + (x[i] == x[i+1]) (i.e. 3 iff adjacent chars are identical, otherwise 2)
g(i, j) = 0 when j < i (this new boundary case is needed)
g(i, j) = g(i+1, j) + g(i, j-1) - g(i+1, j-1) + (x[i] == x[j])*(g(i+1, j-1)+1) when j >= i+2

现在的最终答案就是 g(1, n)。

Answer 3

使用 DP 的直观 O(n^3) 解决方案：

设每个状态dp(i,j)表示string[i...j]中回文子序列的个数那么简单的递归公式就是

for k in range i, j-1:
    if(A[j]==A[k]){
        dp(i,j) = dp(i,j) + dp(k+1,j-1);

想法很简单。添加新角色时检查它是否是子序列的结尾。如果先前计算的较小子问题中存在相同的字符，则它添加范围 (k+1,j-1) 中包含的子序列数。只处理边角情况。添加一个作为新添加的字符也是单个字符子序列。即使 (k+1,j-1) 范围内没有子序列，您仍然会得到 1 个长度为 2 的新子序列（如 "aa"）。

字符串中回文子序列的总数

Total number of palindromic subsequences in a string

algorithm

dynamic-programming

data-structures