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