题解 | #最长回文子序列#

题意整理

• 给定字符串。
• 求这个字符串的最长回文子序列。
• 回文序列是指，如果将原序列翻转后与原序列相等，那么这个序列是回文序列。

方法一（记忆化递归）

1.解题思路

• 递归终止条件：左边界和右边界之间只含一个元素，或只含两个元素。
• 递归如何推进：如果左边界和右边界相等，则可以将两边分别向中间压缩一步，并且长度减二；否则，要么向左压缩，要么向右压缩，取两者较大值。
• 每一层递归返回什么：当前层的最长回文子序列长度。

由于普通的递归会有很多重复的计算，可以用记忆数组记录已知的情况。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    //声明记忆数组
    int[][] memo;

    public int longestPalindromeSubSeq (String s) {
        //转化为字符数组
        char[] arr=s.toCharArray();
        //new一个记忆数组
        memo=new int[arr.length][arr.length];
        //返回左边界为0，右边界为n-1的情况
        return dfs(arr,0,arr.length-1);
    }

    private int dfs(char[] arr,int l,int r){
        //如果记忆数组被赋值过，直接返回
        if(memo[l][r]!=0) return memo[l][r];
        //左边界和有边界在同一位置，即只有一个字符的情况
        if(l==r){
            memo[l][r]=1;
            return 1;
        } 
        //左边界和有边界值相等，且只有左右边界两个索引
        if(l+1==r&&arr[l]==arr[r]){
            memo[l][r]=2;
            return 2;
        }
        //左边界和有边界值相等，可以向中间压缩
        if(arr[l]==arr[r]){
            memo[l][r]=dfs(arr,l+1,r-1)+2;
            return dfs(arr,l+1,r-1)+2;
        }
        //左边界和有边界值不相等，要么压缩左边界，要么压缩右边界
        memo[l][r]=Math.max(dfs(arr,l+1,r),dfs(arr,l,r-1));
        return Math.max(dfs(arr,l+1,r),dfs(arr,l,r-1));
    }


}

3.复杂度分析

• 时间复杂度：最多递归 次，所以时间复杂度是 。
• 空间复杂度：需要额外深度为n的递归栈以及大小为的记忆数组，所以空间复杂度为 。

方法二（动态规划）

1.解题思路

• 状态定义： 表示原字符串起点为i，终点为j的子序列的最长回文子序列的长度。
• 初始化：只要起点和终点在一起，那么最长回文子序列长度就是1。
• 状态转移：如果i索引和j索引处字符相等，那么可以由i+1和j-1分别向左和向右扩散，即 ;如果i索引和j索引处字符不相等，要么取i+1为起点j为终点的串，要么取i为起点j-1为终点的串，即 。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    public int longestPalindromeSubSeq (String s) {
        //初始化dp数组
        int n=s.length();
        int[][] dp=new int[n][n];

        for(int i=n-1;i>=0;i--){
            //如果只有一个字符，长度必为1
            dp[i][i]=1;
            for(int j=i+1;j<n;j++){
                //如果i索引和j索引处字符相等，那么可以由i+1和j-1分别向左和向右扩散
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                //如果不相等，要么取i+1为起点j为终点的串，要么取i为起点j-1为终点的串
                else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        //返回起点为0，终点为n-1之间的最长回文子序列长度
        return dp[0][n-1];
    }
}

3.复杂度分析

• 时间复杂度：需要遍历 次，所以时间复杂度是 。
• 空间复杂度：需要额外大小为的dp数组，所以空间复杂度为 。