最长回文子串

网友投稿 622 2022-11-29

最长回文子串

最长回文子串

最长回文子串问题是求一个序列中最长的回文子串,这个子串可以不连续,如{1, 3, 4, 2, 1}的最长回文子串为{1, 2, 1},典型的区间dp

状态转移方程如下:

当i > j时,dp[i,j]= 0。

当i = j时,dp[i,j] = 1。

当i < j并且str[i] == str[j]时,dp[i][j] = dp[i+1][j-1]+2;

当i < j并且str[i] ≠ str[j]时,dp[i][j] = max(dp[i][j-1],dp[i+1][j]);

由于dp[i][j]依赖i+1,所以循环计算的时候,第一维必须倒过来计算,从len-1到0。

最后,s的最长回文子序列长度为dp[0][len-1]。

#include #include #include #include using namespace std;const int maxn = 1000 + 10;char str[maxn];int dp[maxn][maxn];int main(){ while (cin >> str) { memset(dp, 0, sizeof(dp)); int len = strlen(str); for (int i = len - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < len; j++) { if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]); } } printf("%d\n", dp[0][len - 1]); } return 0;}

下面来将空间复杂度优化到O(n):

我们发现计算第i行时只用到了第i + 1行,因此我们只需要两行即可,即定义dp【2】【maxn】

起初先在第0行计算dp【0】【len - 1】,然后用第0行的结果计算dp【1】【len - 2】,再用第1行的结果在第0行计算dp【0】【len - 3】,以此类推

设正在计算的哪一行为cur,那么计算第cur行时,就要用到第1-cur行的结果

当计算完成时,如果len是奇数,则结果在第0行,如果是偶数,则结果在第1行

#include #include #include #include using namespace std;const int maxn = 1000 + 10;char str[maxn];int dp[2][maxn];int main(){ while (cin >> str) { memset(dp, 0, sizeof(dp)); int len = strlen(str), cur = 0; for (int i = len - 1; i >= 0; i--) { dp[cur][i] = 1; for (int j = i + 1; j < len; j++) { if (str[i] == str[j]) dp[cur][j] = dp[1 - cur][j - 1] + 2; else dp[cur][j] = max(dp[cur][j - 1], dp[1 - cur][j]); } } if (len % 2) printf("%d\n", dp[0][len - 1]); else printf("%d\n", dp[1][len - 1]); } return 0;}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Uva 10048 噪音恐惧症——Floyd变形
下一篇:SpringBoot中Starter的作用小结
相关文章

 发表评论

暂时没有评论,来抢沙发吧~