绝望中诞生的奇迹战士！

解题思路:                                     如果字符不相同取删除，修改，插入的最小值加1

                                                        s  f  d  g  x  b  w  

                                                    0  1  2  3  4  5  6  7                               dp[i-1][j]  删除

                                                g  1  1  2  3  4  5  6  7                               dp[i-1][j-1]  修改

                                                f   2  2  1  2  3  4  5  6                               dp[i][j-1]  插入

                                                d  3  3  2  1  2  3  4  5

                                                g  4  4  3  2  2  3  4  5

                                                w  5  5  4  3  3  4  5  4

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义两个字符串变量，用于存储输入的字符串
string s1, s2;
// 定义一个二维数组dp，用于动态规划计算编辑距离
int dp[2100][2100];
int main() {
    // 读取输入的两个字符串
    cin >> s1 >> s2;
    // 初始化dp数组的第一列，表示将s2的前i个字符转换为空字符串所需的操作数
    for (int i = 1; i <= s2.size(); i++) {
        dp[i][0] = i;
    }
    // 初始化dp数组的第一行，表示将空字符串转换为s1的前i个字符所需的操作数
    for (int i = 1; i <= s1.size(); i++) {
        dp[0][i] = i;
    }
    // 动态规划计算编辑距离
    for (int i = 1; i <= s2.size(); i++) {
        for (int j = 1; j <= s1.size(); j++) {
            // 如果当前字符相同，则不需要额外操作，继承之前的状态
            if (s2[i - 1] == s1[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 如果当前字符不同，取插入、删除和替换三种操作中的最小值加1
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }
    }
    // 输出最终的编辑距离
    cout << dp[s2.size()][s1.size()] << endl;
    return 0;
}