dis*_*kit 6 algorithm dynamic-programming data-structures
问题是这样的 -
对于作为输入给出的每个字符串,您需要告诉它作为回文的子序列的数量(不一定是不同的).请注意,空字符串不是回文.例如,"aab"的回文子序列是:
"a","a","b","aa",方法返回4.
我有动态编程解决方案来寻找最长的回文子序列,因此试图从中获取想法.无法真正得到解决方案.可能甚至不需要动态编程.建议请.
还有一个问题.当"不一定要区分"的条件被删除时,我们仍然可以在不实际产生所有回文子序列的情况下进行计数吗？
j_r*_*ker 13
[编辑19/10/2015:一位匿名审稿人指出公式存在问题,这促使我注意到另一个甚至更大的错误......现在已修复.]
我现在看到如何将解决方案时间降低到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()的其他值来轻松计算在某个确切位置开始或结束的PS的数量,并且可能重新添加更多的g()值来补偿双重数数.例如,恰好在i处开始且在正好 j处结束的PS的数量是g(i,j)-g(i + 1,j)-g(i,j-1)+ g(i + 1,j -1):最后一项纠正了第二项和第三项都计算在 i 之后开始并在 j 之前结束的所有g(i + 1,j-1)PS的事实.
在i之后或之后开始且在j之前或之前结束的每个PS恰好在4个类别中的1个中:
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之后或之后开始并在j-1之前或之前结束的PS一样多,即g(i + 1,j-1),加上一个额外的2字符序列x [I]×[J]. [编辑:感谢评论员Tuxdude在这里进行了2次修复!]
有了这个,我们可以用一种方式表达g(),将二次情形从f()变为恒定时间:
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).