**一. 題目描述** Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2\. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: Insert a character? Delete a character? Replace a character **二. 題目分析** 給定兩個字符串word1和word2，算出講word1轉化成word2所需的最少編輯操作次數。允許的編輯操作包括以下三種： 將一個字符替換成另一個字符? 在字符串中插入一個字符? 刪除字符串中的一個字符 例如將A(abc)轉成B(acbc)： 你可選擇以下操作：? acc （b→c）替換? acb （c→b）替換? acbc （→c）插入 這不是最少編輯次數，因為其實只需要刪除第二個字符`c`就可以了，這樣只需操作一次。 使用`i`表示字符串`word1`的下標（從下標1開始），使用`j`表示字符串`word2`的下標。 用`k[i][j]`來表示`word1[1, ... , i]`到`word2[1, ... , j]`之間的最少編輯操作數。則有以下規律： ~~~ k[i][0] = i; k[0][j] = j; k[i][j] = k[i - 1][j - 1] (if word1[i] == word2[j]) k[i][j] = min(k[i - 1][j - 1], k[i][j - 1], k[i - 1][j]) + 1 (if word1[i] != word2[j]) ~~~ **三. 示例代碼** ~~~ #include <iostream> #include <string> #include <vector> using namespace std; class Solution { public: int minDistance(const string &word1, const string &word2) { const size_t m = word1.size() + 1; const size_t n = word2.size() + 1; vector<vector<int> > k(m, vector<int>(n)); for (size_t i = 0; i < m; ++i) k[i][0] = i; for (size_t j = 0; j < n; ++j) k[0][j] = j; for (size_t i = 1; i < m; ++i) { for (size_t j = 1; j < n; ++j) { if (word1[i - 1] == word2[j - 1]) k[i][j] = k[i - 1][j - 1]; else k[i][j] = min(k[i - 1][j - 1], min(k[i - 1][j], k[i][j - 1])) + 1; } } return k[m - 1][n - 1]; } }; ~~~  **四. 小結** 動態規劃的經典題目，要快速寫出狀態轉移方程還是有點難度的。