前几天交接跟问新同事知道编辑距离吗，同事轻描淡写的就说知道啊，动态规划，给我讲了讲，我心想，卧槽，工大的本硕就是不一样。。。

今天有空赶紧恶补下，之前一直听说动态规划动态规划，也没静下心看，今天终于是仔细看了《算法图解》动态规划的问题，就是小偷偷东西最优解的。。。认真读下来发现这本书讲得还真是不错，把挺复杂的知识清晰简单的讲明白了。

看完了动态规划，又继续看莱文斯坦距离，之前项目测各家语音识别结果的时候用的这个算法，当时第一次感受到算法的不仅好玩，还实用。不过只知道这个算法就是通过对字符串的插入、删除、和替换，计算和另一个字符串的相似度，并不知道原理。

明白了动态规划又仔细看了看代码，终于是理解的差不多了。其实也不难，反正就是会者不难、难者不会。。。

ps：《算法图解》这本书一定得看完

最后贴下源代码，自己写了些注释 

import numpy

def wer2(r, h):
    '''
    This function was originally written by Martin Thoma
    https://martin-thoma.com/word-error-rate-calculation/
    Calculation of WER with Levenshtein distance.
    Works only for iterables up to 254 elements (uint8).
    O(nm) time ans space complexity.
    Parameters
    ----------
    r : list
    h : list
    Returns
    -------
    int
    Examples
    --------
    >>> wer("who is there".split(), "is there".split())
    1
    >>> wer("who is there".split(), "".split())
    3
    >>> wer("".split(), "who is there".split())
    3
    '''
    # Initialization

    #生成一个全是0的二维数组
    d = numpy.zeros((len(r)+1)*(len(h)+1), dtype=numpy.uint8)
    print(d)
    #此时的d形如：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
    #将二维数组变成n*n的格式
    d = d.reshape((len(r)+1, len(h)+1))
    print(d)
    #此时的的形如：
    """
    [[0 0 0 0]
     [0 0 0 0]
     [0 0 0 0]
     [0 0 0 0]]
    """
    #为数组两侧赋值
    for i in range(len(r)+1):
        for j in range(len(h)+1):
            if i == 0:
                d[0][j] = j
            elif j == 0:
                d[i][0] = i
    print(d)
    #此时的d形如：
    """
    [[0 1 2 3]
     [1 0 0 0]
     [2 0 0 0]
     [3 0 0 0]
     ]
    """
    # Computation
    #计算编辑距离
    for i in range(1, len(r)+1):
        for j in range(1, len(h)+1):
            if r[i-1] == h[j-1]:
                d[i][j] = d[i-1][j-1]
            else:
                #替换
                substitution = d[i-1][j-1] + 1
                #插入
                insertion    = d[i][j-1] + 1
                #删除
                deletion     = d[i-1][j] + 1
                print(substitution,insertion,deletion)
                d[i][j] = min(substitution, insertion, deletion)
    print(d)
    #最终的d形如：
    """
    [[0 1 2 3]
     [1 1 2 3]
     [2 2 1 2]
     [3 3 2 2]]
    """
    return d[len(r)][len(h)]
if __name__ == '__main__':
    res=wer2(['c','b','c'],['a','b','d'])
    print(res)

打印结果： 

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[[0 0 0 0]
 [0 0 0 0]
 [0 0 0 0]
 [0 0 0 0]]
[[0 1 2 3]
 [1 0 0 0]
 [2 0 0 0]
 [3 0 0 0]]
1 2 2
2 2 3
3 3 4
2 3 2
3 2 4
3 4 3
3 4 2
2 3 3
[[0 1 2 3]
 [1 1 2 3]
 [2 2 1 2]
 [3 3 2 2]]
2