# Longest Palindromic Subsequence_516

###### tags: `leetcode`,`dp`,`medium`

**Longest Palindromic Subsequence**

>ref: https://leetcode.com/problems/longest-palindromic-subsequence/
>
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.

>0. init : count[i][i]=1 , single word is palindromic.
>count[i][j] define the max length of palindromic string within substring(i,j)
>1. not substring but subsequence, create array store the length of max palindromic length.
>2. calculate count[i][j] after count[i+1][j-1],count[i+1][j] and count[i][j-1]
>3. timeCom:O(MN) spatialCom:O(MN)

    public int longestPalindromeSubseq(String s) {
        
        byte[] t=s.getBytes();
        
        int[][] count= new int[t.length][t.length];
        
        
        for(int i=t.length-1 ; i>=0;i--){
            count[i][i]=1;
            for(int j=i+1;j<t.length;j++){
                if(t[i]==t[j]){
                    count[i][j]=count[i+1][j-1]+2;
                }else{
                    count[i][j]=Math.max(count[i][j-1],count[i+1][j]);
                } 
            }

        }
        
        return count[0][t.length-1];
        
    }