第一章：经典动态规划：编辑距离

labuladong经典动态规划：编辑距离

72. 编辑距离

• 在word1 和word2 前面分别插入"" 不仅可以包括字符串为空的情况，而且可以更清楚地用空字符串说明状态转移的过程
• i 和 j 中，因为最前面加了"", 因此第i个字符的下标为i-1
  • 若两个字符相等（word1[i-1]==word2[j-1]），则i和j分别继续向右跳一格
  • 若不相等，则增（dp[i][j-1]，如第0行），改（dp[i-1][j-1]），删（dp[i-1][j]，如第0列）的最小操作数 +1

class Solution(object):
    def minDistance(self, word1, word2):
        m=len(word1)+1
        n=len(word2)+1
        dp=[[0 for _ in range(n)] for _ in range(m)]
        for j in range(1,n):
            dp[0][j]=j
        for i in range(1,m):
            dp[i][0]=i


        for i in range(1,m):
            for j in range(1,n):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
        return dp[-1][-1]