[UVA] 11584 - Partitioning by Palindromes

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char s[1005];
int dp[1005];
int check(int l,int r){
    int i;
    for(i=0;i<=r-l;i++)
        if(s[l+i]!=s[r-i])
            return 0;
    return 1;
}
int main(){
    int t,i,j;
    scanf("%d",&t);
    while(t--){
        memset(dp,0,sizeof(dp));
        scanf("%s",&s[1]);
        for(i=1;s[i];i++){
            dp[i]=dp[i-1]+1;
            for(j=1;j<=i;j++){
                if(check(j,i)){
                    dp[i]=min(dp[j-1]+1,dp[i]);
                }
            }
        }
        printf("%d\n",dp[i-1]);
    }
}