51nod|51nod oj 1183 编辑距离【求一个字符串到另一个字符串的最小操作次数【类似LCS】】动态规划|我的ACM成长历程---啦

题目链接：1183

此题相当于LCS---下面的看不懂了可以看LCS他们的原理是像似的-

设S串和T串--
我们可以从后面开始看-.-

//如果s[n]==t[m]--那么dp[n][m]=dp[n-1][m-1]--因为一样不操作 //如果s[n]!=t[m]--那么dp[n][m]=min(dp[n-1][m-1],dp[n-1][m],dp[n][m-1])+1 //dp[n-1][m-1]为替换-- //dp[n-1][m]--删s[n]或在t[m]后加一s[n] //dp[n][m-1]--删t[m]或在s[n]后加一t[m]

当dp [ 0 ] [i ]或者 dp [ i ] [ 0 ]时--他们等于i（删除i个或增加i个）

代码：

#include #include #include using namespace std; int dp[1020][1020]; int main() { char a[1020],b[1020]; scanf("%s%s",a,b); int n=strlen(a); int m=strlen(b); memset(dp,0x3f3f3f,sizeof(dp)); for (int i=0; i<1010; i++) dp[i][0]=dp[0][i]=i; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { if (a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1; }printf("%d\n",dp[n][m]); return 0; }

【51nod|51nod oj 1183 编辑距离【求一个字符串到另一个字符串的最小操作次数【类似LCS】】】