Longest Palindromic Subsequence

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".

时间复杂度 和空间复杂度 o(n^2)

class Solution {
    public int longestPalindromeSubseq(String s) {
        if(s == null || s.length() == 0)
            return 0;
        
        int[][] dp = new int[s.length()][s.length()];
        
        for(int len = 1; len <= s.length();len++){
            for(int i = 0; i <= s.length()-len;i++){
               int j = i + len-1;
                
                if(i == j){
                    dp[i][j] = 1;
                    continue;
                }
                
                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][s.length()-1];
    }
}

通过观察可知，不管当si 和sj是不是相等时，他当前dp的值最多用到了len比当前len小2的dp的值，那么可以用三个滚动数组取代dp的二维数组 从而把空间复杂度降到o(n)

class Solution {
    public int longestPalindromeSubseq(String s) {
        if(s == null || s.length() == 0)
            return 0;
        
        int[] dp0 = new int[s.length()];
        int[] dp1 = new int[s.length()];
        int[] dp2 = new int[s.length()];
        
        for(int len = 1; len <= s.length();len++){
            for(int i = 0; i <= s.length()-len;i++){
               int j = i + len-1;
                
                if(i == j){
                    dp0[i] = 1;
                    continue;
                }
                
                if(s.charAt(i) == s.charAt(j)){
                    dp0[i] = dp2[i+1] + 2;
                }else{
                    dp0[i] = Math.max(dp1[i+1] , dp1[i]);
                }
                
                
            }
            //swap 数组 滚动数组，其实就是更改引用
            int[] tmp = dp1;
            dp1 = dp0;
            dp0 = dp2;
            dp2 = tmp;
            
            
        }
        
        
        // dp0 最后被滚动掉了，dp1[0] 就是从i=0开始，len=s.length（）的解
        return dp1[0];
    }
}