编辑距离问题c++，结果输出具体的编辑方法

编辑距离问题是一个经典的动态规划问题，可以使用DP算法来解决。下面给出一个C++的代码实现，同时输出具体的编辑方法。 ```C++ #include <iostream> #include <string> #include <vector> using namespace std; int min(int a, int b, int c) { return min(min(a, b), c); } void printEditMethod(vector<vector<int>>& dp, string s1, string s2) { int m = s1.size(), n = s2.size(); vector<string> method; while (m > 0 && n > 0) { if (s1[m - 1] == s2[n - 1]) { method.push_back("no edit"); m--; n--; } else if (dp[m][n] == dp[m - 1][n - 1] + 1) { method.push_back("replace " + string(1, s2[n - 1])); m--; n--; } else if (dp[m][n] == dp[m - 1][n] + 1) { method.push_back("delete " + string(1, s1[m - 1])); m--; } else if (dp[m][n] == dp[m][n - 1] + 1) { method.push_back("insert " + string(1, s2[n - 1])); n--; } } while (m > 0) { method.push_back("delete " + string(1, s1[m - 1])); m--; } while (n > 0) { method.push_back("insert " + string(1, s2[n - 1])); n--; } for (int i = method.size() - 1; i >= 0; i--) { cout << method[i] << endl; } } int editDistance(string s1, string s2) { int m = s1.size(), n = s2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][j] = j; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; 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], dp[i - 1][j], dp[i][j - 1]) + 1; } } } printEditMethod(dp, s1, s2); return dp[m][n]; } int main() { string s1 = "kitten"; string s2 = "sitting"; int distance = editDistance(s1, s2); cout << "The edit distance between " << s1 << " and " << s2 << " is " << distance << endl; return 0; } ``` 在输出编辑距离的同时，我们定义了一个`printEditMethod`函数，用于输出具体的编辑方法。该函数从`dp`表右下角开始，根据当前格子的值和相邻格子的值来确定编辑方法，直到达到左上角。最后，将方法按照逆序输出即可。