https://leetcode.com/problems/longest-palindromic-subsequence/
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".
d[i][len] = 以 i 开头且长度为 len 的字符串中最长回文串的长度
d[i][len] = max( d[i][len-1], (包含前面一个字符)
d[i+1][len-1], (包含后面一个字符)
d[i][len-2] + 2, (如果 前后字符相等) )
图中的三条箭头分别对应了这三种子情况。
初始条件
d[i][1] = 1;
d[i][2] = 1 (如果不是回文) OR 2 (如果是回文)
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
int d[1005][1005];
for (int i = 0; i < n; i++) {
d[i][1] = 1;
}
for (int i = 0; i < n; i++) {
if (i + 1 >= n) break;
d[i][2] = (s[i] == s[i+1]) ? 2 : 1;
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n; i++) {
if (i + 1 >= n) break;
if (i + len -1 >= n) break;
d[i][len] = max(d[i + 1][len - 1], d[i][len - 1]);
if (s[i] == s[i + len - 1]) {
d[i][len] = max(d[i][len], d[i + 1][len - 2] + 2);
}
}
}
return d[0][n];
}
};
