(编辑距离)给定两个字符串，每次操作可以选择删除(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] = __(1)__ ;


            else if (j == 0)


                dp[i][j] = __(2)__ ;


            else if (__(3)__)


                dp[i][j] = __(4)__ ;


            else


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


        }


    }


    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;


}

选择题