首页 > 代码库 > 51nod 1183 编辑距离(dp)
51nod 1183 编辑距离(dp)
题目链接:51nod 1183 编辑距离
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N = 1001; 6 char a[N], b[N]; 7 int dp[N][N];//dp[i][j]:a串的前i个字符转化成b串的前j个字符的最少操作数 8 int main(){ 9 int i, j; 10 scanf("%s%s", a+1, b+1); 11 int alen = strlen(a+1); 12 int blen = strlen(b+1); 13 for(i = 0; i <= alen; ++i) 14 dp[i][0] = i; 15 for(j = 0; j <= blen; ++j) 16 dp[0][j] = j; 17 for(i = 1; i <= alen; ++i) 18 for(j = 1; j <= blen; ++j) 19 dp[i][j] = min(dp[i-1][j-1] + (a[i]!=b[j]), min(dp[i-1][j]+1, dp[i][j-1]+1)); 20 printf("%d\n", dp[alen][blen]); 21 return 0; 22 }
51nod 1183 编辑距离(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。