dp uva11584

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1000+5;
 5 int n,kase,vis[maxn][maxn],p[maxn][maxn],d[maxn];
 6 char s[maxn];
 7 
 8 int is_palindrome(int i,int j){
 9     if(i>j) return 1;
10     if(s[i] != s[j]) return 0;
11 
12     if(vis[i][j] == kase) return p[i][j];
13     vis[i][j] = kase;
14     p[i][j] = is_palindrome(i+1,j-1);
15     return p[i][j];
16 }
17 
18 int main(){
19     int T;
20     scanf("%d",&T);
21     memset(vis,0,sizeof(vis));
22     for(kase=1; kase<=T; kase++){
23         scanf("%s",s+1);
24         n = strlen(s+1);
25         d[0] = 0;
26         for(int i=1; i<=n; i++){
27             d[i] = i+1;
28             for(int j=0; j<i; j++)
29                 if(is_palindrome(j+1,i))
30                     d[i] = min(d[i],d[j]+1);
31         }
32 
33         printf("%d
",d[n]);
34     }
35 }