最长回文子序列问题的原理与实现：动态规划的又一经典应用-Toy模板网

这篇具有很好参考价值的文章主要介绍了最长回文子序列问题的原理与实现：动态规划的又一经典应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

回文是指一个正着读和反着读都一样的字符串，比如 “aba” ， “racecar” ， “madam” 等。回文有许多有趣的性质和应用，比如在密码学，生物信息学，数据压缩等领域都有涉及。

那么，给定一个字符串，如何找出它的最长回文子序列呢？最长回文子序列是指从原字符串中删除一些元素（也可以不删除）后得到的最长的回文字符串。

例如，对于字符串 “abcbda” ，它的最长回文子序列是 “abba” ，长度为 4 。

最长回文子序列长度问题第一种解法就是求原字符串与其逆序字符串的最大公共子序列长度。关于最大公共子序列长度在上篇博客已经给出解释说明，在这里我们讨论另一种解法。

最长回文子序列问题可以用动态规划算法在多项式时间内解决，其基本思想是利用一个二维数组来存储字符串中任意两个位置之间的最长回文子序列的长度，然后根据递推公式来更新数组的值，最后回溯数组来找出最长回文子序列。

具体来说，假设我们有一个字符串 S = s1s2…sn ，我们定义一个二维数组 L[i,j] 表示 S 的第 i 个元素到第 j 个元素之间的最长回文子序列的长度，则我们有以下递推公式：

如果 i > j ，则 L[i,j] = 0 ，因为空字符串没有回文子序列。
如果 i = j ，则 L[i,j] = 1 ，因为单个字符是回文子序列。
如果 i < j ，则：
- 如果 si = sj ，则 L[i,j] = L[i+1,j-1] + 2 ，因为 si 和 sj 可以作为最长回文子序列的首尾元素。
- 如果 si != sj ，则 L[i,j] = max(L[i+1,j], L[i,j-1]) ，因为 si 和 sj 不可能同时属于最长回文子序列。

根据这个递推公式，我们可以从右下角开始填充数组 L ，直到左上角得到 L[1,n] ，即为 S 的最长回文子序列的长度。然后，我们可以从左上角开始回溯数组 L ，根据以下规则来找出最长回文子序列：

如果 si = sj ，则 si 或 sj 是最长回文子序列的一个元素，将其加入结果中，并向右下方移动一格。
如果 si != sj ，则比较 L[i+1,j] 和 L[i,j-1] 的大小，向较大值所在的方向移动一格。
如果 i > j 或 i = j ，则停止回溯。

下面是一个例子，假设我们有一个字符串 S = “abcbda” ，我们可以按照上述方法求出它的最长回文子序列长度和内容：

S 的最长回文子序列长度为 4 ，且有一个最长回文子序列，即 “abba” 。

下面是用 Python 语言实现的动态规划算法的代码：

def LPSLength(S):
    # 初始化二维数组 L
    n = len(S)
    L = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 填充数组 L
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i > j:
                L[i][j] = 0
            elif i == j:
                L[i][j] = 1
            else:
                if S[i - 1] == S[j - 1]:
                    L[i][j] = L[i + 1][j - 1] + 2
                else:
                    L[i][j] = max(L[i + 1][j], L[i][j - 1])
    
    # 返回最长回文子序列的长度
    return L[1][n]

def LPS(S):
    # 获取二维数组 L
    n = len(S)
    L = LPSLength(S)
    
    # 初始化结果字符串
    result = ""
    
    # 回溯数组 L
    i = 1
    j = n
    while i <= j:
        if S[i - 1] == S[j - 1]:
            result = S[i - 1] + result # 将匹配的元素加入结果中
            i += 1
            j -= 1
        else:
            if L[i + 1][j] > L[i][j - 1]:
                i += 1
            else:
                j -= 1
    
    # 返回最长回文子序列
    return result

# 测试
S = "abcbda"
print(LPSLength(S)) # 输出 4
print(LPS(S)) # 输出 abba

另外，还有一种令人简单理解的递归代码实现：

# 原字符串与其逆字符串的最长公共子序列既是最长回文子序列

# 在l与r范围内最长回文子序列长度
def process(l,r):
    if l==r:
        return 1
    if l==r-1:
        return 2 if s[l]==s[r] else 1
    p1=process(l,r-1)
    p2=process(l+1,r)
    p3=process(l+1,r-1)+2 if s[l+1]==s[r-1] else process(l+1,r-1)
    return max(p1,p2,p3)

def longestHuiwen(s):
    if len(s)==0 and s==None:
        return 0
    if len(s)==1:
        return 1
    if len(s)==2:
        return 2 if s[0]==s[1] else 1

    return process(0,len(s)-1)

s='12a33211'
print(longestHuiwen(s))