本文共 934 字，大约阅读时间需要 3 分钟。

给定一个字符串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
   
    =0; i--){
               for(int j=i+1; j
   

转载地址：http://npwpi.baihongyu.com/