1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=1e3+10,M=1e6+10,inf=1e9+10;
char a[N];
int ans[N][N],x;
int dp(char *a,int len,int beg)
{
    if(len<=0)
    return 0;
    if(ans[beg][len])
    return ans[beg][len];
    if(a[0]==a[len-1])
    return ans[beg][len]=dp(a+1,len-2,beg+1);
    else
    {
        int ans1=dp(a,len-1,beg)+1;
        int ans2=dp(a+1,len-1,beg+1)+1;
        int ans3=dp(a+1,len-2,beg+1)+1;
        return ans[beg][len]=min(min(ans1,ans2),ans3);
    }
}
int main()
{
    int y,z,i,t;
    scanf("%s",a+1);
    x=strlen(a+1);
    dp(a+1,x,1);
    printf("%d\n",ans[1][x]);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX