博客

题目：

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:

输入:
"bbbab"

输出:
4
一个可能的最长回文子序列为 "bbbb"。

示例 2:

输入:
"cbbd"

输出:
2
一个可能的最长回文子序列为 "bb"。

思路：

定义

dp[i][j]

:表示

s[i...j]

之间的最长子序列的长度，注意是子序列，不是子串，子序列是可以跳跃的，子串不可以

当

s[i]==s[j]

时，说明

i

与

j

位置的字符可以形成一个回文，这个回文的长度为

2

,根据dp的思想，其结果应该是依赖前面的结果,也就是

s[i+1 .... j-1]

这个范围的字符回文个数，也就是

dp[i+1][j-1]

，即

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


当

s[i]!=s[j]

时，说明i与j位置的字符不能形成一个回文，这个时候要看

s[i+1...j]s[i+1...j]

与

s[i...j-1]s[i...j−1]

这两段，因为

s[i+1]s[i+1]

可能与

s[i+2...j]s[i+2...j]

范围内的某个字符相同，拼凑出回文，因为

s[i]!=s[j]s[i]!=s[j],

同理可得

s[i...j-1]s[i...j−1]

这段，故此，

dp[i][j]=max[dp[i][j-1]

,

dp[i+1][j]]dp[i][j]=max[dp[i][j−1],dp[i+1][j]]


base case:

很容想到的是

i==j

时，说明

s[i...j]

只有一个字符，此时其自身可以形成一个回文，长度为

1


当

i>j

时，此时是不存在的，因为我们规定了

s[i...j]

起始位置i要小于结束位置j的，此时初始化为

0


代码：

class Solution {
    public int longestPalindromeSubseq(String s) {
        
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
        }

        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        return dp[0][n-1];
    }
}