#include <stdio.h> #include <string.h> // 计算距离的函数 int editDistance(char *str1, char *str2) { // 测量两个字符串的长度 int len1 = strlen(str1); int len2 = strlen(str2); // 动态规划二维数组数组 int dp[len1 + 1][len2 + 1]; for (int i = 0; i <= len1; i++) { // 如果另外一个字符串为空,那么我们需要编辑的长度等于字符串的长度 dp[i][0] = i; } for (int j = 0; j <= len2; j++) { dp[0][j] = j; } // 动态规划计算编辑距离 for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { int cost = (str1[i - 1] == str2[j - 1]) ? 0 : 1; dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost); } } return dp[len1][len2]; } int min(int a, int b) { return a < b ? a : b; } int main() { char str1[1001]; char str2[1001]; scanf("%s", str1); scanf("%s", str2); int distance = editDistance(str1, str2); printf("%d\n", distance); return 0; }