近似串匹配问题动态规划法c++代码实现，用户输入数据，输出结果是两个串的最小差别数

以下是近似串匹配问题的动态规划代码实现（C++）：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];  // dp数组
char s1[MAXN], s2[MAXN];  // 两个字符串

int main() {
    cin >> s1 >> s2;  // 输入两个字符串

    int len1 = strlen(s1), len2 = strlen(s2);  // 字符串长度
    for (int i = 0; i <= len1; i++) dp[i][0] = i;  // 初始化dp数组
    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++) {
            if (s1[i-1] == s2[j-1])  // 字符相同
                dp[i][j] = dp[i-1][j-1];
            else  // 字符不同
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
        }
    }

    cout << dp[len1][len2] << endl;  // 输出最小差别数
    return 0;
}

该代码使用动态规划思想解决最小编辑距离问题，时间复杂度为 $O(n^2)$，其中 $n$ 为两个字符串长度之和。