题目
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".
答案
class Solution {
public int longestPalindromeSubseq(String s) {
int [][] lps = new int[s.length()][s.length()];
for(int i = s.length() - 1; i >= 0; i--) {
for(int j = i; j < s.length(); j++) {
if(i == j)
lps[i][j] = 1;
else if(j == i + 1)
lps[i][j] = (s.charAt(i) == s.charAt(j))?2:1;
else {
if(s.charAt(i) == s.charAt(j))
lps[i][j] = lps[i + 1][j - 1] + 2;
else
lps[i][j] = Math.max(lps[i + 1][j -1], Math.max(lps[i][j - 1], lps[i + 1][j]));
}
}
}
return lps[0][s.length() - 1];
}
}
