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:
a) Insert a character
b) Delete a character
c) Replace a character
思路：
典型的动态规划题，递归要超时哦。状态转移方程：
a[i][j] = min(
1. a[i-1][j] + 1,
2. a[i][j-1] + 1,
3. word1[i] == word2[j] ? a[i-1][j-1] : a[i-1][j-1] + 1
);
C++:
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 5 const int row = word1.size() + 1; 6 const int col = word2.size() + 1; 7 8 int a[row][col]; 9 10 for(int i = 0; i < row; i++) 11 a[i][0] = i; 12 for(int i = 0; i < col; i++) 13 a[0][i] = i; 14 15 for(int i = 1; i < row; i++) 16 for(int j = 1; j < col; j++) 17 a[i][j] = min((word1[i-1] == word2[j-1] ? a[i-1][j-1] : (a[i-1][j-1] + 1)), min(a[i-1][j] + 1, a[i][j-1] + 1)); 18 19 return a[row-1][col-1]; 20 } 21 };
原文：http://www.cnblogs.com/tjuloading/p/4713733.html