poj 1159 回文串问题

给一个串，问最少添加几个字符使得该串变成回文串，dp。。
dp[i][j]表示 i j 的范围内需要添加几个字符，如果 s[i]==s[j],那么 dp[i][j]=dp[i+1][j-1];
否则，dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1
ps: 用short水过，int MLE 啊啊啊啊。。
[cpp]
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=5002;
char s[maxn];
short dp[maxn][maxn];

int main(){
    short n;
    while(scanf("%d",&n)!=EOF){
        scanf("%s",s);
        memset(dp,0,sizeof(dp));
        for(short i=n-1;i>=0;i--)//i指针表示从左端开始
            for(short j=0;j<n;j++){//j指针表示从右端开始
                if(i==j)continue;
                if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];
                else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
            }
        printf("%d\n",dp[0][n-1]);
    }
}

记忆化搜索，卡时过的，效率好低啊。。
[cpp]
#include<stdio.h>
#include<string.h>

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=5002;
char s[maxn];
short dp[maxn][maxn];
short n;

short dfs(short i,short j){
    if(dp[i][j]!=-1)return dp[i][j];
    if(i==n-1||j==0||i==j)return dp[i][j]=0;
    if(s[i]==s[j])return dp[i][j]=dfs(i+1,j-1);
    short a=dfs(i+1,j);
    short b=dfs(i,j-1);
    return dp[i][j]=min(a,b)+1;
}

int main(){

    while(scanf("%d",&n)!=EOF){
        scanf("%s",s);
        //memset(dp,-1,sizeof(dp));
        for(short i=0;i<=n;i++)for(short j=0;j<=n;j++)dp[i][j]=-1;
        dfs(0,n-1);
        printf("%d\n",dp[0][n-1]);
    }
}

作者：qingniaofy

补充：软件开发 , C++ ,