题目分析：

给你word1、word2两个字符串，问最少需要几步才能把word1变成word2，下面每种操作都是一步：

a)添加一个字符；

b)添加一个字符；

c)把一个字符用另一个字符代替。

解题思路：

动态规划。用dpi表示把word1的前i个字符变成word2的前j个字符所需的步数，word1的前i个字符变成word2的前j个字符可以由三种方法得到：

（1）word1先删去最后一个字符，然后把word1的前i-1个字符变成word2的前j个字符；

（2）word1的前i个字符先变成word2的前j-1个字符；然后word2最后添上一个字符；

（3）word1的前i-1个字符先变成word2的前j-1个字符；然后word1的最后一个字符和word2的最后一个字符匹配上。因此有状态转移方程：当word1[i-1]==word2[j-1]时dpi=dpi-1，否则dpi=min(dpi-1+1,dpi+1,dpi-1+1)。另外边界需要初始化：dp0=0，dpi=i对于i从1到len1，dp0=i对于i从1到len2,。最终答案为dplen1，算法复杂度为O(len1*len2)。

算法正确性：

算法的关键点在于是否可以用动态规划的思想把问题拆分成一个个子问题。
可以这么考虑：当你能确定用了若干步把word1的前i个字母变成word2的前j个字母后，接下来就可以处理相邻的状态。对于删除字母，可以把word1的第i+1个字母先删掉，然后再执行那若干步，这样可以得到把word1的前i+1个字母变成word2的前j个字母的步数；对于添加字母，可以先执行那若干步，再加上word2的第j+1个字母，这样可以得到把word1的前i个字母变成word2的前j+1个字母的步数；对于代替字母，可以先执行那若干步，再把word1的第i+1个字母和word2的第j+1个字母匹配上，这样可以得到把word1的前i+1个字母变成word2的前j+1个字母的步数。因此上述算法是正确的。

下面举一个简单例子走一遍算法帮助理解：

word1=”ad”，word2=”abc”。
初始化：dp0=0，dp1=1，dp2=2，dp0=1，dp0=2，dp0=3；
i=1，j=1，word1[0]==word2[0]，dp1=min(dp0+1,dp1+1,dp0)=0；
i=1，j=2，word1[0]!=word2[1]，dp1=min(dp0+1,dp1+1,dp0+1)=2；
i=1，j=3，word1[0]!=word2[2]，dp1=min(dp0+1,dp1+1,dp0+1)=3；
i=2，j=1，word1[1]!=word2[0]，dp2=min(dp1+1,dp2+1,dp1+1)=1；
i=2，j=2，word1[1]!=word2[1]，dp2=min(dp1+1,dp2+1,dp1+1)=1；
i=2，j=3，word1[1]!=word2[2]，dp2=min(dp1+1,dp2+1,dp1+1)=2；
最终结果为dp2=3。

CPP代码

int minDistance(string word1, string word2)
{int len1=word1.size(),len2=word2.size();int dp[len1+1][len2+1];dp[0][0]=0;//初始化边界for(int i=1;i<=len1;i++)//初始化边界{dp[i][0]=i;}for(int i=1;i<=len2;i++)//初始化边界{dp[0][i]=i;}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(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));//两个字符不相等}}return dp[len1][len2];
}