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