学步园

题目链接~~> 

        动态转移方程：dp[i] = min( dp[i] , dp[j-1]+1 )。

代码：

#include<stdio.h>
#include<string.h>
int h ;
char s[1005] ;
int dp[1005] ;
int check(int rt,int le) // 判断是否是回文
{
    while(le<=rt)
    {
        if(s[le++]!=s[rt--])
            return 0 ;
    }
    return 1 ;
}
int main()
{
    int i,j ;
    while(scanf("%s",s+1)!=EOF)
    {
        memset(dp,0,sizeof(dp)) ;
        h=strlen(s+1) ;
        for(i=1 ;i<=h ;i++)
        {
            dp[i]=i ;
            for(j=1 ;j<=i ;j++)
              if(s[i]==s[j]&&check(i,j))
              {
                  dp[i]=dp[i] < dp[j-1]+1 ? dp[i] : dp[j-1]+1 ;
                  break ;   // 加个break ；稍微快点
              }
        }
        printf("%d\n",dp[h]) ;
    }
    return 0 ;
}