1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 5001 6 #define INF 0x3f3f3f3f 7 char str[MAXN]; 8 short dp[2][MAXN]; 9 10 11 int getmin(int x, int y) {12     return x<y ? x:y;13 }14 15 int main() {16     int n;17     int i, j, k;18 19     while (scanf("%d", &n) != EOF) {20         scanf("%s", str+1);21         memset(dp, 0, sizeof(dp));22         for (i=n; i>0; --i) {23             k = i&1;24             for (j=i+1; j<=n; ++j) {25                 if (str[i] == str[j]) {26                     dp[k][j] = dp[!k][j-1];27                 } else {28                     dp[k][j] = getmin(dp[!k][j], dp[k][j-1]) + 1;29                 }30             }31         }32         printf("%d\n", dp[1][n]);33     }34 35     return 0;36 }