POJ_1159 Palindrome （线性动态规划+滚动数组）

题意是说，给定一个字符串，问至少还需要插入多少个字符才能使得该字符串成为回文字符串。

这道题一开始做的时候用了一个简单的动态规划，开了一个5000*5000的数组，用递归形式实现，代码如下：

其中d[i][j]表示i到j所需要插入的字符数。然而数组开得太大直接报MLE。因此想到用滚动数组来解决。

MLE代码如下：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

//内存超限 MLE

const short maxn=+;

int d[maxn][maxn];//d表示i到j形成回文串所需加入的字符数

string s;

int dp(int i,int j){

    if(d[i][j]>=)return d[i][j];

    if(i<j){

        if(s[i]==s[j]){

            d[i][j]=dp(i+,j-);

            return d[i][j];

        }

        else{

            d[i][j]=min(dp(i+,j),dp(i,j-))+;

            return d[i][j];

        }

    }

    else if(i==j){

        d[i][j]=;

        return ;

    }

}

int main(void){

    int n;

    scanf("%d",&n);

    cin>>s;

    memset(d,-,sizeof(d));

    int ans=dp(,n-);

    cout<<ans<<endl;

    return ;

}

使用滚动数组的动态规划和上述略有不同。基本算法如下：

设输入为X，则记X的逆序列为Y，其中X的字符个数为n,

那么ans=n-(X和Y的最大公共子序列长度）。这样就将该问题转化为了求最长公共子序列的问题。

则此时令d[i][j]表示为X序列和Y序列在前I项和前j项的最大公共序列的长度。

具体状态转移方程见代码或最长公共子序列题的动态转移方程。

但此时的d[i][j]仍然是5000*5000的数组，而由状态转移方程可以发现，在递推过程中其实只涉及两层数组内容，因此可以只保留两层数组从而将数组减小为2*5000的滚动数组。

AC代码如下：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

//线性动态规划，滚动数组

const int maxn=+;

int d[][maxn];

int main(void){

    int n;

    while(cin>>n){

        string s1,s2;

        cin>>s1;

        s2=s1;

        reverse(s1.begin(),s1.end());

        memset(d,,sizeof(d));

        int n=s1.length();

        for(int i=;i<=n;i++){

            for(int j=;j<=n;j++){

                if(s1[i-]==s2[j-]){

                    d[i%][j]=d[(i-)%][j-]+;

                }

                else{

                    d[i%][j]=max(d[(i-)%][j],d[i%][(j-)]);

                }

            }

        }

        cout<<n-d[n%][n]<<endl;

    }

    return ;

}

巴特西

POJ_1159 Palindrome （线性动态规划+滚动数组）

最新文章

热门文章