本文共 1605 字，大约阅读时间需要 5 分钟。

题目：

解答：

编程之美上有解答，如果采用递归的方法，会超时。

解答一，采用递归，代码：

class Solution {  public:	  int minDistance(string word1, string word2) {		  return calculate(word1, word2);	  }	  int calculate(string word1, string word2)	  {		  if (word1 == "")		  {			  if (word2 == "")				  return 0;			  else				  return word2.length();		  }		  if (word2 == "")		  {			  if (word1 == "")				  return 0;			  else				  return word1.length();		  }		  if (word1[0] == word2[0])		  {			  string w1 = word1.substr(1, word1.length() - 1);			  string w2 = word2.substr(1, word2.length() - 1);			  return calculate(w1, w2);		  }		  else		  {			  string w1 = word1.substr(1, word1.length() - 1);			  string w2 = word2.substr(1, word2.length() - 1);			  int t1 = calculate(w1, word2);			  int t2 = calculate(word1, w2);			  int t3 = calculate(w1, w2);			  int minval = min(t1, t2);			  minval = min(t3, minval);			  return minval + 1;		  }	  }  };

动态规划，http://www.cnblogs.com/lihaozy/archive/2012/12/31/2840152.html。

代码：

class Solution {  public:	  int minDistance(string word1, string word2) {		  int row = word1.length() + 1;		  int col = word2.length() + 1;		  vector
   
    
      > f(row, vector
     
      (col));		  for (int i = 0; i < row; i++)			  f[i][0] = i;		  for (int i = 0; i < col; i++)			  f[0][i] = i;		  for (int i = 1; i < row; i++)		  {			  for (int j = 1; j < col; j++)			  {				  if (word1[i-1] == word2[j-1])					  f[i][j] = f[i - 1][j - 1];				  else				  {					  f[i][j] = f[i - 1][j - 1] + 1;					  f[i][j] = min(f[i][j], min(f[i - 1][j] + 1, f[i][j - 1] + 1));				  }			  }		  }		  return f[row - 1][col - 1];	  }  };