近似串匹配动态规划法c++代码，要求自己输入数据

以下是使用动态规划实现的近似串匹配算法的C++代码，其中包含用户输入数据的功能：

#include <iostream>
#include <string>

using namespace std;

const int MAX_N = 1000;

int dp[MAX_N + 1][MAX_N + 1];

int main() {
    string s, t;
    cin >> s >> t;

    const int INF = 100000000;
    int n = s.size(), m = t.size();

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i > 0) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            }
            if (j > 0) {
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
            }
            if (i > 0 && j > 0) {
                int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cost);
            }
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

该程序首先读入两个字符串s和t，并定义一个二维数组dp来存储最小编辑距离。设置dp[i][j]表示将s的前i个字符转换为t的前j个字符所需的最小编辑距离。

然后，将dp数组中的所有值初始化为一个较大的数字INF，这样可以确保在计算过程中不会出现无限大的值。将dp[0][0]设为0，表示将一个空字符串转换为另一个空字符串的编辑距离为0。

接下来，使用两个for循环计算dp数组的值。对于每个dp[i][j]，计算三种情况：

- 将s的前i-1个字符转换为t的前j个字符所需的最小编辑距离加1，得到dp[i][j]的值。
- 将s的前i个字符转换为t的前j-1个字符所需的最小编辑距离加1，得到dp[i][j]的值。
- 将s的前i-1个字符转换为t的前j-1个字符所需的最小编辑距离加上将s的第i个字符替换为t的第j个字符所需的代价（1或0），得到dp[i][j]的值。

最后，输出dp[n][m]，即将s转换为t所需的最小编辑距离。