1 /*此程序实现功能：输入两串字符s1，s2，求出其编辑距离。编辑距离：表示插入一个字符，删除一个字符，替换一个字符使得一个字符串和另一个字符串相等，三种操作分别表示1*/ 2 /*算法思想：动态规划*/ 3 #include<iostream> 4 #include<string> 5 using namespace std; 6 template <typename T> T min(T a, T b, T c) { 7     if (a < b&&a < c) 8         return a; 9     else10         if (b < c)11             return b;12         else13             return c;14 }15 int EditDistance(string s1, string s2);//求编辑距离16 int main() {17     string s1 , s2;18     cout << "请输入字符串s1:";  cin >> s1; cout << endl;19     cout << "请输入字符串s2:";  cin >> s2; cout << endl;20     cout << "s1与s2的编辑距离是：" << EditDistance(s1, s2) << endl;21     //delete s1, s2;22 }23 int EditDistance(string s1, string s2) {24     //m[|s1|][|s2|]是一个二维数组，矩阵第i行第j列的元素保存的是s1的前i个字符和s2的前j个字符的编辑距离25     // 分配行指针数组26     int x = 0;27     int **m = new int*[s1.length() + 1];28     // 分配列指针数组29     for (int i = 0; i < s1.length() + 1; i++) {30         m[i] = new int[s2.length() + 1];31         //初始化，将数组的第一列每行设为对应的值，即假设s2是一个空串32         m[i][0] = i;33     }34     //初始化，将数组的第一列每行设为对应的值，即假设s2是一个空串35     for (int j = 0; j < s2.length() + 1; j++)36         m[0][j] = j;37     //动态规划核心算法：min中的三个参数分别表示在s1中替换一个，插入一个和在s2中插入一个（即在s1中删除一个）的操作38     for (int i = 1; i < s1.length() + 1; i++) {39         40         for (int j = 1; j < s2.length() + 1; j++) {41             x = 0;42             if (s1[i - 1] != s2[j - 1])43                 x = 1;44             m[i][j] = min<int>(m[i - 1][j - 1] + x, m[i - 1][j] + 1, m[i][j - 1] + 1);45         }46     }47     x = m[s1.length()][s2.length()];48     for (int i = 0; i < s1.length() + 1; i++)49         delete[] m[i];50     return x;51 }