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
思路：
典型的动态规划题目。我是按照dp的解法来解的，初始化需要注意。假设word1的长度为a,word2的长度为b，那么需要开辟一个二维数组dp[a+1][b+1]，其中第一行代表一个空的word1通过添加变成word2所需的步骤，第一列代表word1通过删除变成word2的步骤。因此dp[i][0]=i;dp[0][j]=j.有关这个的具体的可以参考这篇博客。
题解：
class Solution { public: int minDistance(string word1, string word2) { int len1 = word1.size(); int len2 = word2.size(); int **dp = new int *[len1+1]; for(int i=0;i<=len1;i++) dp[i] = new int [len2+1]; for(int i=0;i<=len1;i++) //word1变成空的word2 dp[i][0] = i; for(int j=0;j<=len2;j++) //word2变成空的word1 dp[0][j] = j; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1]; else { dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1; } } return dp[len1][len2]; } };
原文：http://www.cnblogs.com/jiasaidongqi/p/4233272.html
