1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 100 + 10; 8 9 int n; 10 char s1[maxn], s2[maxn]; 11 12 int d[maxn][maxn], a[maxn]; 13 14 int main() 15 { 16 while(scanf("%s%s", s1 + 1, s2 + 1) == 2) 17 { 18 n = strlen(s1 + 1); 19 for(int i = 1; i <= n; i++) d[i][i] = 1; 20 21 for(int l = 2; l <= n; l++) 22 for(int i = 1; i + l - 1 <= n; i++) 23 { 24 int j = i + l - 1; 25 d[i][j] = d[i + 1][j] + 1; 26 for(int k = i + 1; k <= j; k++) if(s2[i] == s2[k]) 27 d[i][j] = min(d[i][j], d[i+1][k-1] + d[k][j]); 28 } 29 30 if(s1[1] == s2[1]) a[1] = 0; else a[1] = 1; 31 for(int i = 2; i <= n; i++) 32 { 33 a[i] = d[1][i]; 34 if(s1[i] == s2[i]) a[i] = a[i - 1]; 35 else 36 { 37 for(int j = 1; j < i; j++) a[i] = min(a[i], a[j] + d[j+1][i]); 38 } 39 } 40 41 printf("%d ", a[n]); 42 } 43 44 return 0; 45 }