HJ52_计算字符串的编辑距离_动态规划

思路：

该题目符合最优解拥有最优子解，符合动态规划算法要求.

 2 思路：操作方法有3种，替换、插入、删除。把a字符串编辑成b字符串的距离。
 3 假设空字符串开始编辑作为bottom 边界。
 4 a字符串作为深度，b作为宽度。
 5 沿宽度遍历为add,沿深度遍历为delete,斜角为change
 6 判断是否相同，相同则取三个数最小值+1,不同则取最小值。

可视化：

程序：

 1 '''
 2 思路：操作方法有3种，替换、插入、删除。把a字符串编辑成b字符串的距离。
 3 假设空字符串开始编辑作为bottom 边界。
 4 a字符串作为深度，b作为宽度。
 5 沿宽度遍历为add,沿深度遍历为delete,斜角为change
 6 判断是否相同，相同则取三个数最小值+1,不同则取最小值。
 7 '''
 8 
 9 a='ucyfsmg'
10 b='zuixhuhyjgksyhqkjqxwylkoubykjxtcvkyqjpzgltbemmbmqibxxqpkgbvwbmjotixanvciibubglizmumcrjavakiygyuv'
11 dp=[[i for i in range(len(b)+1)]for j in range(len(a)+1)]
12 for i in range(len(a)+1):
13     dp[i][0]=i
14 for i in range(1,len(a)+1):
15     for j in range(1,len(b)+1):
16         if a[i-1]==b[j-1]:
17             dp[i][j]=dp[i-1][j-1]#注意：这里不能取3个数最小值！！！
18         else:
19             dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
20 print(dp[len(a)][len(b)])

526互联

HJ52_计算字符串的编辑距离_动态规划_动态规划可视化