疑惑点1
-
删除操作对应 f(i−1,j)
如果要从字符串 A 中删除一个字符,相当于从 A 的前 i 个字符中删除第 i 个字符,然后与 B 的前 j 个字符匹配。因此,删除操作将状态从f(i,j) 转移到 f(i−1,j),并且增加一次操作。 -
插入操作对应 f(i,j−1)
如果要在字符串 A 中插入一个字符,使其匹配 B 中的第 j 个字符,相当于在 A 的前 i 个字符后面插入 B 的第 j 个字符,然后与 B 的前 j-1 个字符匹配。因此,插入操作将状态从
f(i,j) 转移到 f(i,j−1),并且增加一次操作。 -
替换操作对应 f(i−1,j−1)
如果要将 A 中的第 i 个字符替换为 B 中的第j个字符,相当于将两个字符都改变(如果它们不同),然后匹配 A 的前 i-1 个字符和 B 的前 j-1 个字符。因此,替换操作将状态从f(i,j) 转移到f(i−1,j−1),并且增加一次操作(如果字符不同)。
举出具体的例子
假设字符串 A 为 “horse”,字符串 B 为 “ros”。我们使用动态规划表格来计算最小操作次数。
初始状态:
f = [
[0, 1, 2, 3],
[1, 0, 0, 0],
[2, 0, 0, 0],
[3, 0, 0, 0],
[4, 0, 0, 0],
[5, 0, 0, 0]
]
计算过程
当 i=1, j=1:
A 的第 1 个字符为 ‘h’
B 的第 1 个字符为 ‘r’
f[1][1]=min(f[0][1]+1,f[1][0]+1,f[0][0]+1)=min(2,2,1)=1
当 i=1, j=2:
A 的第 1 个字符为 ‘h’
B 的第 2 个字符为 ‘o’
f[1][2]=min(f[0][2]+1,f[1][1]+1,f[0][1]+1)=min(3,2,2)=2
当 i=1, j=3:
A 的第 1 个字符为 ‘h’
B 的第 3 个字符为 ‘s’
f[1][3]=min(f[0][3]+1,f[1][2]+1,f[0][2]+1)=min(4,3,3)=3
继续填充表格,最终得到:
f = [
[0, 1, 2, 3],
[1, 1, 2, 3],
[2, 2, 1, 2],
[3, 3, 2, 2],
[4, 4, 3, 3],
[5, 4, 4, 3]
]