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

Question

问题是这样的--

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

“a”、“a”、“b”、“aa”，方法返回 4。

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

还有一个问题。当“不一定是不同的”条件被移除时，我们是否仍然可以在不实际生成所有回文子序列的情况下进行计数？

Answer 1

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

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

与其计算恰好在位置 i 和 j 开始和结束的 PS 的数量，不如计算有多少开始于或之后 i 并结束于或之前 j.称之为 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 的情况。但这并不完全有效，因为前两个术语将重复计算在之后 i 开始并在之前 j 结束的任何 PS。

关键的洞察力是注意到我们可以通过减去 g() 的其他值，并可能添加更多的g() 返回以补偿重复计算。例如，从恰好 i 开始到恰好 j 结束的 PS 的数量是 g(i, j) - g(i+1, j) - g( i, j-1) + g(i+1, j-1):最后一项纠正了这样一个事实，即第二项和第三项都计算了以 开头的所有 g(i+1, j-1) PS在 i 之后和在 j 之前结束。

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

1. 开始于 i 之后，结束于 j 之前。
2. 它从 i 开始，到 j 之前结束。
3. 它从 i 开始，到 j 结束。
4. 它从 i 开始，到 j 结束。

g(i+1, j) 统计了类别 1 或 3 中的所有 PS，而 g(i, j-1) 统计了类别 1 或 2 中的所有 PS，因此它们的和 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类的PS。如果x[i] != x[j]则该类没有PS；否则，从 i+1 或 i+1 开始并在 j-1 或之前结束的 PS 的数量与 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)。