http://info.zjfc.edu.cn/acm/contest/contest_problemDetail.aspx?pid=1002&cid=29
//15344 2009-04-24 21:46:41 1002  Accepted 125MS 7984K Visual C++ xredman 
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
bool dp[2001][2001];//dp[i][j]標志從i到j這段串是否為回文
char str[2001];
int f[2001];//f[i]表示從1到i最少的回文數
int main()
{    
    while(scanf("%s",str+ 1)!=EOF)
    {
        int len,i,j,mins;
        len = strlen(str+1);

        for(i=1;i<=len;i++)
            for(j=1;j<=len;j++)
                dp[i][j] = 0;

        for(i=1;i<=len;i++)
            dp[i][i] = 1;

        for(i=2;i<=len;i++)
            if(str[i] == str[i-1])
                dp[i-1][i] = 1;

        for(i=3;i<=len;i++)//長度
        {
            for(j=1;j<=len-i+1;j++)
            {
                if(str[j] == str[j+i-1] && dp[j+1][j+i-2] == 1)
                    dp[j][j+i-1] = 1;
            }
        }
        if(dp[1][len] == 1)
            printf("1\n");
        else
        {
            f[1] = 1;
            for(i=2;i<=len;i++)
            {
                mins = i;
                if(dp[1][i] == 1)
                {
                    f[i] = 1;
                    continue;
                }
                for(j=1;j<i;j++)
                {
                    if(dp[j+1][i] == 1 && mins > f[j] + 1)
                        mins = f[j] + 1;
                }
                f[i] = mins;
            }
            printf("%d\n",f[len]);
        }
    }
    return 0;
}