20. （完善程序）

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

试补全动态规划算法。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int min(int x, int y, int z) {
    return min(min(x, y), z);
}

int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = _________________________;
            else if (j == 0)
                dp[i][j] = _________________________;
            else if (_________________________)
                dp[i][j] = _________________________;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], _________________________);
        }
    }
    return dp[m][n];
}

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Mininum number of operation:"  << edit_dist_dp(str1, str2) << endl;
    return 0;
}

① 处应填（ ）。

{{ select(1) }}

• j
• i
• m
• n

② 处应填（ ）。

{{ select(2) }}

• j
• i
• m
• n

③ 处应填（ ）。

{{ select(3) }}

• str1[i - 1] == str2[j - 1]
• str1[i] == str2[j]
• str1[i - 1] != str2[j - 1]
• str1[i] != str2[j]

④ 处应填（ ）。

{{ select(4) }}

• dp[i - 1][j - 1]+1
• dp[i - 1][j - 1]
• dp[i - 1][j]
• dp[i][j - 1]

⑤ 处应填（ ）。

{{ select(5) }}

• dp[i][j]+1
• dp[i - 1][j - 1]+1
• dp[i - 1][j - 1]
• dp[i][j]