在这个问题的几个dp解决方案中,一个更简单的解决方案是反转给定的字符串并计算原始和反向字符串的LCS.
我的问题是这种方法每次会产生正确的结果吗？
例如,ACBAC及其反向CABCA的最长公共子序列是ABC,它不是回文,但由于其他LCS是回文ACA,CAC,这仍然给出了正确的结果.
那么,即使可能存在非回文LCS,这种方法每次都能产生正确的结果吗？
dp表,如果有帮助的话.
A C B A C
0 0 0 0 0 0
C 0 0 1 1 1 1
A 0 1 1 1 2 2
B 0 1 1 2 2 2
C 0 1 2 2 2 3
A 0 1 2 2 3 3