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[i][j]表示以S[i]结尾的字符串和以T[j]结尾的字符串转换所需的最小操作数，考虑三种操作，然后取三者最小值：
1、替换：
假设S[i-1],T[j-1]已对齐，即dp[i-1][j-1]已知，则当S[i]==T[j]时，dp[i][j]=dp[i-1][j-1]，否则，dp[i][j]=dp[i-1][j-1]+1.
2、删除
假设S[i-1]，T[j]已对齐，即dp[i-1][j]已知，多出来的S[i]需删除，操作数+1，则dp[i][j]=dp[i-1][j]+1.
3、插入
假设S[i],T[j-1]已对齐，即dp[i][j-1]已知，需在S中插入S[i+1]=T[j]来匹配，操作数+1，则dp[i][j]=dp[i][j-1]+1.
状态转移方程：
dp[i][j]=min(dp[i-1][j-1]+(S[i]==T[j]?0,1),dp[i-1][j]+1,dp[i][j-1]+1)
初始值：
dp[i][0]=i
dp[0][j]=j
复杂度：
时间复杂度：O(m*n)
空间复杂度：O(m*n)
空间优化：
由状态转移方程可知，dp[i][j]与dp[i-1][j-1],dp[i-1][j],dp[i][j-1]有关，可以去掉一维，只留下dp[j]。
等式右边的dp[i-1][j]和dp[i][j-1]都可以直接改成dp[j]（旧的值）和dp[j-1]（已更新），只有dp[i-1][j-1]没有记录下来，通过某个变量保存起来之后就可以。
因此空间复杂度：O(n)
见程序注释