《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(40)翻天印压回文串 - 最长回文子序列(区间DP)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的回文森林,森林中有一本古老的翻天印,印身闪烁着神秘的光芒。森林的入口处有一块巨大的石碑,上面刻着一行文字:“欲破此林,需以翻天印之力,压回文串,区间DP显真身。”
哪吒定睛一看,石碑上还有一行小字:“字符串"bbbab"
的最长回文子序列长度为4
,例如"bbbb"
。”哪吒心中一动,他知道这是一道关于最长回文子序列的难题,需要通过区间动态规划的方法来解决。
暴力解法:翻天印的初次尝试
哪吒心想:“要找到最长回文子序列,我可以逐个字符比较。”他催动翻天印之力,从字符串的第一个字符开始,逐个字符比较,试图找到最长的回文子序列。
int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n, 0));for (int i = 0; i < n; ++i) {dp[i][i] = 1;}for (int i = n - 1; i