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
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int i, j, k, len, dp[100][100];
    char s[110];
    cin >> s;
    len = strlen(s);
    dp[0][0] = 0;
    for(j=1; j<len; ++j)
    {
        dp[j][j] = 0;
        dp[j-1][j] = (s[j-1] != s[j]);
        for(i=j-2; i>=0; --i)
        {
            dp[i][j] = 1 + min(dp[i][j-1], dp[i+1][j]);
            dp[i][j] = min(dp[i][j], (s[i]!=s[j]) + dp[i+1][j-1]);
        }
    }
    cout << dp[0][len-1];
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX