字符串的修改动归解法

解题思路:动态规划算法

注意事项:

使用一个二维数组 dp来存储中间结果，其中 dp[i][j]表示将字符串A的前i个字符转换为字符串B的前j个字符所需的最少字符操作次数。通过动态规划的方式计算出 dp[m][n]，即将整个字符串A转换为整个字符串B所需的最少字符操作次数。其中， m和n分别表示字符串A和字符串B的长度。 程序中的 min函数用于计算三个数的最小值。在动态规划的过程中，根据字符是否相等来决定进行删除、插入还是替换操作，并选择操作次数最少的方式。

参考代码:

#include <stdio.h>

#include <string.h>

#define MAX_LEN 100

int min(int a, int b, int c) { //根据字符是否相等来选择最小次数操作

    int min = a;

    if (b < min) {

        min = b;

    }

    if (c < min) {

        min = c;

    }

    return min;

}

int minDistance(char* A, char* B) {

    int m = strlen(A);

    int n = strlen(B);

    int dp[m+1][n+1]; //dp[i][j] 表示将字符串A的前i个字符转换为B的前j个字符所需最少操作次数

    for (int i = 0; i <= m; i++) {

        dp[i][0] = i;

    }

    for (int j = 0; j <= n; j++) {

        dp[0][j] = j;

    }

    for (int i = 1; i <= m; i++) {

        for (int j = 1; j <= n; j++) {

            if (A[i-1] == B[j-1]) {

                dp[i][j] = dp[i-1][j-1];

            } else {

                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1;

            }

        }

    }

    return dp[m][n];

}

int main() {

    char A[MAX_LEN];

    char B[MAX_LEN];

    scanf("%s", A);

    scanf("%s", B);

    int result = minDistance(A, B);

    printf("%d\n", result);

    return 0;

}