题意:给你两个字符串s1,s2。让你通过给s1涂色,使s1变成s2。涂色的方式只能每次给一个区间图一种颜色。
只考虑s1和s2不存在相同的字母的情况:
dp[i][j]表示区间(i,j)涂色的次数。
dp[i][j]=min(dp[i+1][j]+1,dp[i+1][k]+dp[k+1][j]);
有几种方法:
1.单独给i涂色 dp[i+1][j]+1
2.如果存在s2[i]==s2[k],可以把i和k一起涂色 dp[i+1][k]+dp[k+1][j]
考虑s1和s2存在相同的字母的情况:
ans[i]表示区间[0,i]涂色的次数
1.如果s1[i]==s2[i],ans[i]==ans[i-1];
2.ans[i]=min(ans[j]+dp[j+1][i]);可以分成区间[0,j]和区间[j+1,i]分别涂色。
代码:
#include<iostream> #include<vector> #include<string> #include<queue> #include<map> #include<cstdio> #include<cstring> #define maxn 105 #define INF 0xfffffff #define min(a,b) a<b?a:b #define max(a,b) a>b?a:b using namespace std; char s1[maxn],s2[maxn]; int dp[maxn][maxn]; int ans[maxn]; int main() { int i,j,k,len; while(scanf("%s %s",s1,s2)!=EOF) { //若s1和s2完全不相同的情况下最少变的次数 len=strlen(s1); memset(dp,0,sizeof(dp)); for(j=0;j<len;j++) { for(i=j;i>=0;i--) { dp[i][j]=dp[i+1][j]+1;//开始时把i单独刷 for(k=i+1;k<=j;k++) { if(s2[i]==s2[k]) dp[i][j]=min(dp[i][j],(dp[i+1][k]+dp[k+1][j]));//如果i和k颜色相同,i和k一起刷 } } } for(i=0;i<len;i++)//ans[i]表示[0,i]涂色 ans[i]=dp[0][i]; for(i=0;i<len;i++) { if(s1[i]==s2[i]) { ans[i]=ans[i-1]; } else { for(j=0;j<i;j++) ans[i]=min(ans[i],ans[j]+dp[j+1][i]); } } printf("%d\n",ans[len-1]); } return 0; }