#1323 : 回文字符串
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个字符串 S ，最少需要几次增删改操作可以把 S 变成一个回文字符串？
一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符。
输入
字符串 S。S 的长度不超过100, 只包含'A'-'Z'。
输出
最少的修改次数。
- 样例输入
-
ABAD
- 样例输出
-
1
思路：经典动态规划题目。
假设f(s[1..n])表示把长度为n的字符串s改写成回文串需要的操作。
如果s[1] == s[n]，那么f(s[1..n]) = f(s[2..n-1])。
否则f(s[1..n])是以下三种情况的最小值：
1. 在s[n]后添加一个字符匹配s[1]，f(s[1..n]) = 1 + f(s[2..n])。
2. 在s[1]前添加一个字符匹配s[n], f(s[1..n]) = 1 + f(s[1..n-1])。
3. 把s[1]和s[n]其中一个修改为另外一个使其匹配，f(s[1..n]) = 1 + f(s[2..n-1])。
需要记忆话，不然超时#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=1e3+,M=1e6+,inf=1e9+;
char a[N];
int ans[N][N],x;
int dp(char *a,int len,int beg)
{
if(len<=)
return ;
if(ans[beg][len])
return ans[beg][len];
if(a[]==a[len-])
return ans[beg][len]=dp(a+,len-,beg+);
else
{
int ans1=dp(a,len-,beg)+;
int ans2=dp(a+,len-,beg+)+;
int ans3=dp(a+,len-,beg+)+;
return ans[beg][len]=min(min(ans1,ans2),ans3);
}
}
int main()
{
int y,z,i,t;
scanf("%s",a+);
x=strlen(a+);
dp(a+,x,);
printf("%d\n",ans[][x]);
return ;
}