It is a typical DP problem. let's use a[i][j] represent the longest Palindromic Subsequence of S[i:j] (i,j inclusive).

So a[i][j]=

(1) a[i+1][j-1]+2 if S[i] == S[j]

(2) Max( a[i+1][j], a[i][j-1] ) if S[i]! = S[j]

```
public class Solution {
public int longestPalindromeSubseq(String s) {
int n=s.length();
int[][] a=new int[n][n];
for(int i=0;i<n;i++) a[i][i]=1;
return helper(a,0,n-1,s);
}
private int helper(int[][] a,int i,int j,String s){
if(i>j || a[i][j]!=0) return a[i][j];
if(s.charAt(i)==s.charAt(j)) a[i][j]=helper(a,i+1,j-1,s)+2;
else a[i][j]=Math.max(helper(a,i,j-1,s),helper(a,i+1,j,s) );
return a[i][j];
}
}
```