// Recursive: Time Limit Exceeded Error
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
return helper(s, 0, n - 1);
}
private int helper(String s, int lo, int hi) {
if (lo > hi) return 0;
if (lo == hi) return 1;
int max = 0;
for (int i = lo; i < hi; i++) {
for (int j = hi; j >= i; j--) {
if (j - i + 1 < max) return max;
if (i == j) {
max = Math.max(max, 1);
break;
}
if (s.charAt(i) == s.charAt(j)) {
max = Math.max(max, 2 + helper(s, i + 1, j - 1));
break;
}
}
}
return max;
}
}
// Dynamic Programming
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
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][n - 1];
}
}