这里仅讨论相同长度的两个单词之间的最小编辑距离。（两个不同长度的单词之间的最小编辑距离待探索）

对于一个字符来说，插入操作的cost为1，删除操作的cost为1，替换操作的cost为2（等同于先删除再插入）

以stay修改为play为例，我们可以构建如下的二维数组储存实时的最小的cost。

#   # s t a y
# # 0 1 2 3 4
# p 1 2 3 4 5
# l 2 3 4 5 6
# a 3 4 5 4 5
# y 4 5 6 5 4

首先，第一行代表从空插入到某个str1字符串的代价，第一列代表从空一直插入到某个str2字符串的代价，显然这个代价与当前考虑到的字符串长度相同。（从空插入一个长度为n的字符串，代价为n）

其次，状态转移方程为：

• 插入代价 = 当前步考虑到的两个字符串其中任意一个去掉最后一位的代价 + 1
• 删除代价 = 当前步考虑到的两个字符串其中任意一个去掉最后一位的代价 + 1
• 替换代价 = 当前步考虑到的两个字符串分别去掉最后一位 + 2 *（当前步考虑到的两个字符串最后一位是否相同）

根据上述状态转移方程可以写出如下实时cost代码：

#求出动态规划矩阵matrix,并返回最小cost

def min_edit_distance_cost(str1 , str2):
    matrix = []
    length = len(str1)
    #初始化矩阵
    for i in range(length + 1):
        matrix.append([0] * 5)
    for i in range(length + 1):
        matrix[0][i] = i
        matrix[i][0] = i

    for i in range(1 , length + 1):
        for j in range(1 , length + 1):
            insert_cost = matrix[i][j - 1] + 1
            delete_cost = matrix[i - 1][j] + 1
            replace_cost = 0
            if(str1[i - 1] == str2[j - 1]):
                replace_cost = matrix[i - 1][j - 1]
            else:
                replace_cost = matrix[i - 1][j - 1] + 2
            matrix[i][j] = min(insert_cost , delete_cost , replace_cost)
    print(matrix)
    cost = matrix[length][length]
    return cost