C++ :

#include<iostream>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<cmath>
#include<string>
#include<cstdio>
using namespace std;

const int N = 1010;
char s[N];
int dp[N][N];

int main() {
    while(~scanf("%s", s)) {
        int n = strlen(s);
        for(int i = 0; i < n; ++i) {
            dp[i][i] = 1;
            if(s[i] == s[i+1]) dp[i][i+1] = 1;
            else dp[i][i+1] = 2;
        }
        for(int len = 2; len < n; ++len)
            for(int i = 0; i < n; ++i) {
                int j = i + len;
                if(s[i] == s[j] && dp[i+1][j-1] == 1) dp[i][j] = 1;
                else dp[i][j] = dp[i+1][j-1] + 2;
                for(int k = i; k < j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        printf("%d\n", dp[0][n-1]);
    }
    return 0;
}