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
#include <bits/stdc++.h>
using namespace std;
string str;
int dp[101][101];
int dfs(int i, int j){
    
    if(i > j || i == j) return 0;
    if(dp[i][j] != 0x3f3f3f3f) return dp[i][j];
    if(str[i] == str[j]) dp[i][j] = dfs(i + 1, j - 1);
    else{
        dp[i][j] = min(dp[i][j], dfs(i, j - 1) + 1);
        dp[i][j] = min(dp[i][j], dfs(i + 1, j) + 1);
        dp[i][j] = min(dp[i][j], dfs(i + 1, j - 1) + 1);
    }
    return dp[i][j];
}
int main(){
    cin >> str;
    memset(dp, 0x3f, sizeof(dp));
    cout << dfs(0, str.length() - 1) << endl;
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX