Longest parlidrome

516. Longest Palindromic Subsequence Medium

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

解法1: 这个题可以想象为 两个字符串，一个正向一个反向，求去 longest common subsequence

class Solution {
    public int longestPalindromeSubseq(String s) {
        return lcs(s, 0, s.length()-1, new Integer[s.length()][s.length()]);
    }
    private int lcs(String s,int left,int right,Integer[][] mem){
        if(left>=s.length() || right<0) return 0;
        if(mem[left][right]!=null) return mem[left][right];
        if(s.charAt(left) == s.charAt(right)){
            mem[left][right]=lcs(s, left+1, right-1, mem)+1;
        }
        else{
             mem[left][right]= Math.max(lcs(s, left+1, right,mem), lcs(s,left, right-1,mem));
        }
        return mem[left][right];
    }
}

解法2: 另外一个是dp 想法

这个视频讲的非常好https://www.youtube.com/watch?v=_nCsPn7_OgI

状态转移方程：

if arr[left] = arr[right]  : mem[left][right] = mem[left+1][right-1]+2;

else  mem[left][right] = max(mem[left][right-1], mem[left+1][right]);

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] mem = new int[s.length()][s.length()];
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<=s.length()-i;j++){
                if(i == 1) {
                    mem[j][j+i-1] = 1;
                    continue;
                }
                if(s.charAt(j) == s.charAt(j+i-1)) 
                    mem[j][j+i-1] = mem[j+1][j+i-2]+2;
                else{
                    mem[j][j+i-1] = Math.max(mem[j+1][j+i-1], mem[j][j+i-2]);
                }
            }
        }
        return mem[0][s.length()-1];
    }
}