Medium
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".
讲解：
Dynamic Programming | Set 12 (Longest Palindromic Subsequence)
dp[i][j]表示substring s[i, j]所包含的longest palindrome的长度。首先初始化长度为1的substring所包含的longest palindrome的长度, 也就是dp[i][i] = 1. 然后看长度为2的,长度为3的……，当s.chatAt(i) == s.charAt(j)的时候，dp[i][j] = dp[i + 1][j - 1] + 2, 因为首尾字符串相同的话，相当于多了2个；如果s.charAt(i) != s.charAt(j)的话，则dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]).比如字符串BABACDB的子串BABAC里面找dp[0][4]的时候，因为s.charAt(0) != s.charAt(4), 所以就等于BABA, ABAC当中palindrome较长的, 这里都是3。
注意一下初始化的index, i是从大到小n - 1到0，j是从i + 1到n,不这么写的话后面会很麻烦，可以记一下。
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
//substring of length 1 has the longest palidrome substring of length 1
for (int i = 0; i < n; i++){
dp[i][i] = 1;
}
for (int i = n - 1; i >= 0; i--){
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 {
//if s.chatAt(i) != s.charAt(j), then the longest palindrome length of s(i,j) is the max of s(i+1,j) ,s(i,j-1)
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}
