首页 > 代码库 > POJ 1159 回文LCS滚动数组优化
POJ 1159 回文LCS滚动数组优化
详细解题报告可以看这个PPT
这题如果是直接开int 5000 * 5000 的空间肯定会MLE，优化方法是采用滚动数组。
原LCS转移方程 ：
dp[i][j] = dp[i - 1][j] + dp[i][j -1]
因为 dp[i][j] 只依赖于 dp[i - 1][j] 和 dp[i][j - 1]
所以可以采用滚动数组如下：
dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[i % 2][j - 1]
可以实现节省空间的方法
答案存储在 dp[n % 2][n] 中
source code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 500;int dp[2][5005];int main(){ int i, j, t, k, n, m; string str1, str2; while(EOF != scanf("%d",&n)){ cin >> str1; str2 = str1; reverse(str1.begin(), str1.end()); memset(dp, 0, sizeof(dp)); for(i = 1; i <= n; ++i){ for(j = 1; j <= n; ++j){ if(str1[i - 1] == str2[j - 1]){ dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - 1] + 1); } else{ dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]); } } } cout << n - dp[n % 2][n] << endl; //answer = X.length() - LCS(X, Y) } return 0;}
POJ 1159 回文LCS滚动数组优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。