最长回文子串

最长回文子串

最长回文子串问题是求一个序列中最长的回文子串，这个子串可以不连续，如{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小时内删除侵权内容。