首页 > 代码库 > [luoguP2758] 编辑距离（DP）
[luoguP2758] 编辑距离（DP）
传送门
f[i][j] 表示第一串前 i 个到第二串前 j 个的最小编辑距离
f[i][j] = f[i - 1][j - 1] (s1[i] == s2[j])
f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) (s1[i] != s2[j])
边界 f[0][j] = j (1 <= j <= m)
f[i][0] = i (1 <= i <= n)
——代码
1 #include <cstdio> 2 #include <cstring> 3 4 int n, m; 5 int f[2048][2048]; 6 char s1[2048], s2[2048]; 7 8 inline int min(int x, int y) 9 {10 return x < y ? x : y;11 }12 13 int main()14 {15 int i, j;16 scanf("%s %s", s1 + 1, s2 + 1);17 n = strlen(s1 + 1);18 m = strlen(s2 + 1);19 for(i = 1; i <= n; i++) f[i][0] = i;20 for(i = 1; i <= m; i++) f[0][i] = i;21 for(i = 1; i <= n; i++)22 for(j = 1; j <= m; j++)23 {24 if(s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1];25 else f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;26 }27 printf("%d\n", f[n][m]);28 return 0;29 }
[luoguP2758] 编辑距离（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。