/*
dp[l][r]表示将任意串的[l,r]刷成s2样子的最小代价
ans[i]表示将s1的前i位刷成s2的代价
按照区间dp的常用做法，dp[l][r]的状态由dp[l][k],dp[k+1][r]决定
若s2[l]==s2[k]，那么在刷k的时候也能刷到l，dp[l][r]=min(dp[l][r],dp[l+1][k]+dp[k+1][r])
但是有可能所有的s[k]！=s[l],即s2[l]要被单独刷一次，那么dp[l][r]要被赋初值dp[l][r]=1+dp[l+1][r]
第二步计算ans数组,若s1[i]==s2[i],那么第i位就不用刷，即ans[i]=ans[i-1]
否则ans[i]=min(ans[i],ans[k]+dp[k+1][i]);
*/
#include<bits/stdc++.h>
using namespace std;
char s1[
200],s2[
200];
int dp[
200][
200],ans[
200],n;
int main(){
while(scanf(
"%s%s",s1,s2)==
2){
n=
strlen(s1);
memset(dp,0,
sizeof dp);
for(
int r=
0;r<n;r++)
//右边界
for(
int l=r;l>=
0;l--){
//左边界依次拓展
dp[l][r]=dp[l+
1][r]+
1;
for(
int k=l+
1;k<=r;k++
)
if(s2[l]==s2[k])
//只要将刷左子区间和刷右子区间的值合并即可
dp[l][r]=min(dp[l][r],dp[l+
1][k]+dp[k+
1][r]);
}
for(
int i=
0;i<n;i++
)
ans[i]=dp[
0][i];
for(
int i=
0;i<n;i++
)
if(s1[i]==s2[i])ans[i]=ans[i-
1];
else {
for(
int j=
0;j<i;j++
)
ans[i]=min(ans[i],ans[j]+dp[j+
1][i]);
}
printf("%d\n",ans[n-
1]);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10319332.html
相关资源：各显卡算力对照表！
