动态规划最小编辑距离python代码

如果是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=1d[i-1][j]、d[i][j-1]、d[i-1][j-1]进行比较，其中最小的就是当前A和B的编辑距离