转载

最长回文子序列

最长回文子序列

题目

给定一个字符串s,找到其中最长的回文子序列

例如输入:bbbab,最大回文子序列长度为4,结果为bbbb

分析

? 题目其实和最大公共子序列很相似。比较字符串的第一个字符 s 1 s_1 和最后一个字符 s n s_n ,如果

它们相等。则原问题 F ( 1 , n ) F(1,n) 最优解为 F ( 2 , n ? 1 ) + 2 F(2,n-1)+2 , F ( 2 , n ? 1 ) F(2,n-1) s 2 , s 3 , s n ? 1 s_2, s_3, s_{n-1} 字符串的最大回文子序列

如果不相等 F ( 1 , n ) = m a x { F ( 1 , n ? 1 ) , F ( 2 , n ) } F(1,n)=max\{F(1,n-1), F(2, n)\} 。以下是python代码的实现

自底向上的方法

#代码leetcode超时,以后改进
class Solution:      
    def longestPalindromeSubseq(self, s):
        """ :type s: str :rtype: int """
        n = len(s)
        dp = [[0 for i in range(n+1)] for i in range(n+1)]
        
        for i in range(1, n+1): dp[i][i] = 1
        
        for i in range(1, n):
            for j in range(1, n-i+1):
                ia, ja = j, j+i
                #print (ia, ja)
                if s[ia-1] == s[ja-1]:
                    dp[ia][ja] = dp[ia+1][ja-1] + 2
                else:
                    dp[ia][ja] = max(dp[ia+1][ja], dp[ia][ja-1])
        
        return dp[1][n]

备忘录方法

class Solution:
    def digui(self, s, i, j, dp):
        #print (i, j)
            
        if i == j: return 1
        
        if i > j: return 0
            
        if s[i-1] == s[j-1]:
            
            if dp[i+1][j-1] == -1:
                dp[i+1][j-1] = self.digui(s, i+1, j-1,dp)
            
            dp[i][j] = dp[i+1][j-1] + 2
        
        else:
            if dp[i+1][j] == -1:
                dp[i+1][j] = self.digui(s, i+1, j, dp)
            
            if dp[i][j-1] == -1:
                dp[i][j-1] = self.digui(s, i, j-1, dp)
            
           
            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        
        return dp[i][j]
        
    def longestPalindromeSubseq(self, s):
        """ :type s: str :rtype: int """
        n = len(s)
        dp = [[-1 for i in range(n+1)] for i in range(n+1)]
        
        for i in range(1, n+1): dp[i][i] = 1
        
        self.digui(s, 1, n, dp)
        
        return dp[1][n]
正文到此结束
本文目录