本文主要是介绍TZOJ 1072: 编辑距离(动态规划)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1072: 编辑距离 
时间限制(普通/Java):1000MS/10000MS 内存限制:65536KByte
总提交: 917 测试通过:275
描述
假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。
例如：a="ABC",b="CBCD",则a与b的编辑距离为2。
你的任务就是：编一个快速的程序来计算任意两个字符串的编辑距离。
输入
输入包含多组测试数据。每组测试数据一行，为字符串A和字符串B。
字符串的长度不大于1024，且全为字母。
输出
编辑距离。
样例输入
ABC CBCD
样例输出
2
提示
我相信动态规划算法能解决这题，因为我就是这样做的。^_^
题目来源
ZJGSU
#include<stdio.h>
#include<string.h>
int dp[1029][1029];
int main()
{char str1[1029],str2[1029];while(scanf("%s%s",str1,str2)>0){int len1,len2;len1=strlen(str1);len2=strlen(str2);for(int i=0;i<=len2;i++)//注意初始化dp[0][i]=i;for(int i=0;i<=len1;i++)dp[i][0]=i;for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++)if(str1[i-1]==str2[j-1]){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=dp[i-1][j]+1;//册除字符str1[i]if(dp[i][j-1]+1<dp[i][j])dp[i][j]=dp[i][j-1]+1;//添加字符str2[j]到str1if(dp[i-1][j-1]+1<dp[i][j])dp[i][j]=dp[i-1][j-1]+1;//把str1[i]变成str2[j]}printf("%d\n",dp[len1][len2]);}
}
这篇关于TZOJ 1072: 编辑距离(动态规划)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
