文件名称：动态规划-最小编辑距离 python代码
文件大小：993B
文件格式：PY
更新时间：2021-08-17 08:26:25
动态规划
如果是A串的第i个字符和B串的第j个字符 1.在A的第i个字符后插入一个字符B[j]，问题转化为计算A[i...lenA]和B[j+1...lenB]的距离 2.删除A串的第i个字符，问题转化为计算A[i+1...lenA]和B[j...lenB]的距离 3.将A的第i个字符替换成B的第j个字符，问题转化为计算A[i+1...lenA]和B[j+1...lenB]的距离。于是替换操作的编辑距离就是d[i-1][j-1]+flag。其中，当A[i]==B[j]时，flag=0， A[i]！=B[j]，flag=1 d [i-1][j] 、d [i][j-1]、d [i-1][j-1]进行比较，其中最小的就是当前A和B的编辑距离