InputInput contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.
OutputA single line contains one integer representing the answer.Sample Input
zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd
Sample Output
6 7
思路:我们考虑到将空白串刷成2串的代价 = 将当前第i号所在的区间i,j 刷成和 2 串相同的代价(一串的i！=2串的i)
f[i][j]表示将空白串刷成2串的代价 考虑 i状态
如果枚举断点k 串2 的 i == 串2 的 k 那么就可以不用更新
同理
ans[i] 表示 1到i 区间 所耗费最小代价
如果 i 号的串相等 那么就不用刷
如果不相等 那么就枚举断点 后面是刷空串的代价
code:
// #include<bits/stdc++.h> using namespace std; #define maxnn 200 int f[maxnn][maxnn],ans[maxnn]; int n; string str1,str2; int main() { while(cin>>str1>>str2) { int n=str2.size(); for(int i=0;i<n;i++) f[i][i]=1; for(int i=n-2;i>=0;i--) for(int j=i+1;j<n;j++) { f[i][j]=f[i+1][j]+1; for(int k=i+1;k<=j;k++) if(str2[k]==str2[i]) f[i][j]=min(f[i][j],f[i+1][k-1]+f[k][j]); } for(int i=0;i<=n;i++) { ans[i]=f[0][i]; if(str1[i]==str2[i]) { if(i==0)ans[i]=0; else ans[i]=ans[i-1]; } for(int k=0;k<i;k++) { ans[i]=min(ans[i],ans[k]+f[k+1][i]); } } cout<<ans[n-1]<<endl; } }
原文：https://www.cnblogs.com/OIEREDSION/p/11272845.html