1 //Accepted    300 KB    31 ms 2 //区间dp 思路完全网上看的 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 105; 8 int dp[imax_n][imax_n]; 9 char s1[imax_n],s2[imax_n];10 int ans[imax_n];11 int n;12 int min(int a,int b)13 {14     return a<b?a:b;15 }16 void Dp()17 {18     memset(dp,0,sizeof(dp));19     for (int i=1;i<=n;i++)20     dp[i][i]=1;21     dp[0][0]=0;22     for (int i=1;i<n;i++)23     {24         if (s2[i-1]==s2[i])25         dp[i][i+1]=1;26         else27         dp[i][i+1]=2;28     }29     for (int l=3;l<=n;l++)30     {31         for (int i=1;i<=n;i++)32         {33             int j=i+l-1;34             if (j>n) break;35             dp[i][j]=dp[i+1][j]+1;36             for (int k=i+1;k<=j;k++)37             if (s2[i-1]==s2[k-1])38             dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);39         }40     }41 }42 int main()43 {44     while (scanf("%s%s",s1,s2)!=EOF)45     {46         n=strlen(s1);47         Dp();48         ans[0]=0;49         for (int i=1;i<=n;i++)50         {51             ans[i]=dp[1][i];52             if (s1[i-1]==s2[i-1])53             ans[i]=ans[i-1];54             for (int k=0;k<i;k++)55             ans[i]=min(ans[i],ans[k]+dp[k+1][i]);56         }57         printf("%d\n",ans[n]);58     }59     return 0;60 }

 1 //Accepted    300 KB    15 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 const int imax_n = 105; 7 int dp[imax_n][imax_n]; 8 char s1[imax_n],s2[imax_n]; 9 int ans[imax_n];10 int n;11 int min(int a,int b)12 {13     return a<b?a:b;14 }15 void Dp()16 {17     //memset(dp,0,sizeof(dp));18     for (int i=1;i<=n;i++)19     dp[i][i]=1;20     dp[0][0]=0;21     for (int i=1;i<n;i++)22     {23         if (s2[i-1]==s2[i])24         dp[i][i+1]=1;25         else26         dp[i][i+1]=2;27     }28     for (int l=3;l<=n;l++)29     {30         for (int i=1;i<=n;i++)31         {32             int j=i+l-1;33             if (j>n) break;34             if (s2[i-1]==s2[j-1])35             dp[i][j]=dp[i+1][j];36             else37             dp[i][j]=dp[i+1][j]+1;38             for (int k=i+1;k<j;k++)39             if (s2[i-1]==s2[k-1])40             dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);41         }42     }43 }44 int main()45 {46     while (scanf("%s%s",s1,s2)!=EOF)47     {48         n=strlen(s1);49         Dp();50         ans[0]=0;51         for (int i=1;i<=n;i++)52         {53             ans[i]=dp[1][i];54             if (s1[i-1]==s2[i-1])55             ans[i]=ans[i-1];56             for (int k=0;k<i;k++)57             ans[i]=min(ans[i],ans[k]+dp[k+1][i]);58         }59         printf("%d\n",ans[n]);60     }61     return 0;62 }