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;
}