描述

---

给定一个字符串 S ，最少需要几次增删改操作可以把 S 变成一个回文字符串？

一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符。

输入

---

字符串 S。S 的长度不超过100, 只包含'A'-'Z'。

输出

---

最少的修改次数。

样例输入

ABAD

样例输出

1

题解

---

dp[l][r]为区间（l，r）的最小编辑数

dp[l][r]=dp[l-1][r+1] //a[l]==a[r] ---1

dp[l][r]=min(dp[l-1][r]+1,dp[l][r-1]+1) // ---2

dp[l][r]=（1，2中较小一个）

#include <map>

#include <queue>

#include <cmath>

#include <cstdio>

#include <complex>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 1000000000000000000LL

#define PI acos(-1)

#define REP(i,x,n) for(int i=x;i<=n;i++)

#define DEP(i,n,x) for(int i=n;i>=x;i--)

#define mem(a,x) memset(a,x,sizeof(a))

using namespace std;

ll read(){

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

void Out(int a){

    if(a<0) putchar('-'),a=-a;

    if(a>=10) Out(a/10);

    putchar(a%10+'0');

}

const int N=105;

int dp[N][N];

char str[N];

int solve(int l,int r){

     if(l>=r) return 0;

     if(dp[l][r]!=-1) return dp[l][r];

     int ans;

     ans=solve(l+1,r-1);

     if(str[l]!=str[r]) ans=min(ans,min(solve(l+1,r),solve(l,r-1)))+1;

     return dp[l][r]=ans;

}

int main(){

    scanf("%s",str);

    mem(dp,-1);

    Out(solve(0,strlen(str)-1));

    puts("");

    return 0;

}