力扣516. 最长回文子序列
动态规划
- 思路：
- 字符串最长回文子序列问题可以转换为原字符串 s 和逆串 s' 的最长公共子序列长度问题，具体推断过程可以参考 力扣1312. 让字符串成为回文串的最少插入次数
- 问题变成了求两个字符串最长公共子序列长度问题，具体思路可以参考 力扣1143. 最长公共子序列
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
std::string invs(s.rbegin(), s.rend());
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
if (s[i - 1] == invs[j - 1]) {
dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[n][n];
}
};————————————————————
原文地址：https://blog.csdn.net/N_BenBird/article/details/135890238
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！