我开始读题的时候以为弄错提了。。看来读题还是有待提高 题意是 给定两个串，一个a，b，让a变成b 有两种操作 1 增加一个字符 2 减少一个字符 3 转换一个字符 每一次操作算一次操作数， 问你最小的操作数 在华南农业大学的acm群里有人问这道题，后来翻了翻，还是挺有意思的，开始以为是最长公共子串，后来大神说有修改最长公共子串毛啊，还发了wiki的连接，大致分为三种 dp[i][j]表示从 a串中i长的子串 到 b串中j长的字串的变化需要操作数。 不怎么显然的是，如果i,j有一个为0，那么操作数就是 不为0的那个数，j或者i; 否则的话有 状态转移方程如代码。 具体看 方程 poj不支持 bits/stdc++ …
//#include <bits/stdc++.h> #include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn=1005; //是一个dp的题，因为有修改操作，所以不是 //最长公共子串这么简单的事情啊 /*并且惊奇的发现一个规律，那就是两个串相互转化，操作一样， 设置dp[i][j]，长度为i的子串1 变成长度为j 的子串2 所花费的。 1 当有i和j有一个为1时，那么就等于那个不为1的+f[i][j]； （很简单啊，你只能删啊或者加啊（逆向）） 如果在中间呢，考虑一个 dp状态方程吧 dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+f[i][j]; */ int a1,b1; char a[maxn],b[maxn]; int f[maxn][maxn]; int dp[maxn][maxn]; int DP() { memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); int t=min(a1,b1); for(int i=1;i<=a1;i++) for(int j=1;j<=b1;j++) f[i][j]=(a[i-1]==b[j-1])? 0 :1;//如果相等就不用了 /*for(int i=0;i<a1;i++) {for(int j=0;j<b1;j++) printf("%d ",f[i][j]); cout<<endl; } cout<<"**************"<<endl;*/ for(int i=1;i<=a1;i++) { dp[i][0]=i; }//初始化一样吧，就是这个套路。 for(int i=1;i<=b1;i++) dp[0][i]=i; for(int i=1;i<=a1;i++) { for(int j=1;j<=b1;j++) { dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+f[i][j]); //自己理解，讲了就没意思了 //好吧我还是讲吧，我自己都不咋理解。 /*为什么 第一个要 dp[i-1][j] 呢，因为达到这个状态就是直接添上i一个字符哦 而第二个加一，是添加 j一个字符，（都是添加），最后那个判断，如果f[i][j]有， 就说明最后一位相等，那么以前的就相当于插入的，这个不动。 */ } } /*for(int i=0;i<a1;i++) {for(int j=0;j<b1;j++) printf("%d ",dp[i][j]); cout<<endl; }*/ cout<<dp[a1][b1]<<endl; } int main() { while(cin>>a1>>a) {cin>>b1>>b; DP();} return 0; }