516. Longest Palindromic Subsequence.md

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1: Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".

Example 2: Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".

class Solution:
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s)==0:
            return 0
        if len(s)==1:
            return 1
        dp=[[0 for i in range(len(s))] for j in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-2,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])
        return dp[0][len(s)-1]

算法解析：

二维dp的题目，存放第i个字母到第j个字母的回文数长度

i from len(s)-2 to 0:

​ j from i+1 to len(s)-1:

​ if s[i]==s[j]:

​ dp[i][j]=dp[i+1][j-1]+2

​ else:

​ dp[i][j]=max(dp[i+1][j],dp[i][j-1])

Return dp[0][len(s)-1]