《編程之美》第223頁。 # 題目描述 ????? 許多程序會大量使用字符串。對于不同的字符串，我們希望能夠有辦法判斷其相似程序。我們定義一套操作方法來把兩個不相同的字符串變得相同，具體的操作方法為： 1.修改一個字符（如把“a”替換為“b”）;　　 2.增加一個字符（如把“abdd”變為“aebdd”）; 3.刪除一個字符（如把“travelling”變為“traveling”）; 比如，對于“abcdefg”和“abcdef”兩個字符串來說，我們認為可以通過增加/減少一個“g”的方式來達到目的。上面的兩種方案，都僅需要一 次 。把這個操作所需要的次數定義為兩個字符串的距離，而相似度等于“距離+1”的倒數。也就是說，“abcdefg”和“abcdef”的距離為1，相似度 為1/2=0.5。 給定任意兩個字符串，你是否能寫出一個算法來計算它們的相似度呢？ # 采用遞歸方法求解 原文的分析與解法　　 　　不難看出，兩個字符串的距離肯定不超過它們的長度之和（我們可以通過刪除操作把兩個串都轉化為空串）。雖然這個結論對結果沒有幫助，但至少可以知道，任意兩個字符串的距離都是有限的。我們還是就住集中考慮如何才能把這個問題轉化成規模較小的同樣的子問題。如果有兩個串A=xabcdae和B=xfdfa，它們的第一個字符是 相同的，只要計算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距離就可以了。但是如果兩個串的第一個字符不相同，那么可以進行 如下的操作（lenA和lenB分別是A串和B串的長度）。 1.刪除A串的第一個字符，然后計算A[2,...,lenA]和B[1,...,lenB]的距離。 2.刪除B串的第一個字符，然后計算A[1,...,lenA]和B[2,...,lenB]的距離。 3.修改A串的第一個字符為B串的第一個字符，然后計算A[2,...,lenA]和B[2,...,lenB]的距離。 4.修改B串的第一個字符為A串的第一個字符，然后計算A[2,...,lenA]和B[2,...,lenB]的距離。 5.增加B串的第一個字符到A串的第一個字符之前，然后計算A[1,...,lenA]和B[2,...,lenB]的距離。 6.增加A串的第一個字符到B串的第一個字符之前，然后計算A[2,...,lenA]和B[1,...,lenB]的距離。 在這個題目中，我們并不在乎兩個字符串變得相等之后的字符串是怎樣的。所以，可以將上面的6個操作合并為： 1.一步操作之后，再將A[2,...,lenA]和B[1,...,lenB]變成相字符串。 2.一步操作之后，再將A[2,...,lenA]和B[2,...,lenB]變成相字符串。 3.一步操作之后，再將A[1,...,lenA]和B[2,...,lenB]變成相字符串。 通過以上1和6,2和5，3和4的結合操作，最后兩個字符串每個對應的字符會相同，但是這三種操作產生的最終的兩個字符串是不一樣的。我們不知道通過上述的三種結合那種使用的操作次數是最少的。所以我們要比較操作次數來求得最小值。 下面這幅圖是摘自編程之美：從中我們可以看出一些信息。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 可以看到，在計算的過程中，有索引越界的情況，抓住這個特點，就可以盡早的結束程序，同時還有重復計算的情況，比如(strA, 2, 2, strB, 2, 2). # 動態規劃方法求解 利用二維數組代替函數遞歸調用。 # 代碼 ~~~ #include <string> #include <iostream> #include <vector> using namespace std; //求三個數的最小值 int min(int a, int b, int c) { if (a > b) { if (b > c) return c; else return b; } if (a > c) { if (c > b) return b; else return c; } if (b > c) { if (c > a) return a; else return c; } } //使用動態規劃求解方法 int StringDistance(string &str1, int start1, int end1, string &str2, int start2, int end2) { if (start1 > end1) { if (start2 > end2) return 0; else return end2 - start2 + 1; } if (start2 > end2) { if (start1 > end1) return 0; else return end1 - start1 + 1; } if (str1[start1] == str2[start2]) return StringDistance(str1, start1 + 1, end1, str2, start2 + 1, end2); else { int t1 = StringDistance(str1, start1 + 1, end1, str2, start2, end2); int t2 = StringDistance(str1, start1, end1, str2, start2 + 1, end2); int t3 = StringDistance(str1, start1 + 1, end1, str2, start2 + 1, end2); return min(t1, t2, t3) + 1; } } //遞歸求解方法 int StringDistance(string &str1, string &str2) { int len1 = str1.length(), len2 = str2.length(); vector<vector<int> > ivec(len1 + 1, vector<int>(len2 + 1)); //下面初始化的含義： //當str1長度為0時，那么兩個字符串的距離就是str2的長度 //同樣，當str2長度為0， 那么兩個字符串距離就是str1的長度 for (int i = 0; i < len1 + 1; ++i) ivec[i][0] = i; for (int i = 0; i < len2 + 1; ++i) ivec[0][i] = i; for(int i = 1; i <= len1; ++i) { for (int j = 1; j <= len2; ++j) { if (str1[i - 1] == str2[j - 1]) ivec[i][j] = ivec[i - 1][j -1]; else ivec[i][j] = min(ivec[i][j - 1], ivec[i - 1][j], ivec[i - 1][j - 1]) + 1; } } return ivec[len1][len2]; } int main() { string str1, str2; cin >> str1 >> str2; //int dis = StringDistance(str1, 0, str1.length() - 1, str2, 0, str2.length() - 1); int dis = StringDistance(str1, str2); cout << dis << endl; } ~~~ [http://blog.csdn.net/zzran/article/details/8274735](http://blog.csdn.net/zzran/article/details/8274735)