圖片.png
-
基本思想：
名詞解釋：什么是回文子序列晨抡？就是說一個(gè)字符串中可以忽略幾個(gè)char但是最終還是會(huì)成為回文序列：
例如：bbaababb:
可以忽略這個(gè)a雏吭，這樣就是一個(gè)最長(zhǎng)的回文字符串
圖片.png -
算法解釋：
圖片.png
abba:是一個(gè)標(biāo)準(zhǔn)回文 長(zhǎng)度是4
abbax:最后的x可以忽略 結(jié)果還是4.
C++：下面的代碼是兩種做法见剩，一種是標(biāo)準(zhǔn)的dp:dp[i][j]代表從i到j(luò)最長(zhǎng)長(zhǎng)度
方法二：len 和dp 代表算法解釋中的兩種情況：
//int longestPalindromeSubseq(string s) {
// int n = s.size();
// vector<vector<int>> dp(n, vector<int>(n));
// for (int i = n - 1; i >= 0; --i) {
// dp[i][i] = 1;
// for (int j = i + 1; j < n; ++j) {
// if (s[i] == s[j]) {
// dp[i][j] = dp[i + 1][j - 1] + 2;
// }
// else {
// dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
// }
// }
// }
// return dp[0][n - 1];
//}
//faster
int longestPalindromeSubseq(string s) {
vector<int> dp(s.size(), 1);
int n = s.size();
int len = 0;
for (int i = n - 1; i >= 0; i--) {
len = 0;
for (int j = i + 1; j < n; j++) {
int t = dp[j];
if (s[i] == s[j]) {
dp[j] = len + 2;
}
len = max(len, t);
}
}
int ans = 0;
for (auto aa : dp)
ans = max(ans, aa);
return ans;
}
