正文
poj 1159 dp回文串
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
题意:添加最少的字符使之成为回文串
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,m,t;
short dp[maxn][maxn];
char s[maxn];
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int len=;
scanf("%d",&len);
scanf("%s",s);
for(i=;i<len;i++) dp[i][i]=;
for(k=;k<len;k++)
{
for(i=;i+k<=len;i++)
{
int j=k+i;
if(s[i]==s[j]) dp[i][j]=dp[i+][j-];
else dp[i][j]=min(dp[i+][j],dp[i][j-])+;
}
}
printf("%d\n",dp[][len-]);
return ;
}