hand8.pdf

背景：比较两个string 的近似性

需要从最小的代价，从第一个单词到第二个单词。→ 编辑距离

先填空串比较容易

T(m,0)=m

T(0,n)=n

考虑SN和SU 之间的距离， 需要考虑

$$ (SN,S)+1 \\(S,SU）+1\\(S,S)+1 $$

向上比， 删除

向左比，增加

斜上方比，替换

$$ T(m,n)=\min\{T(m-1,n)+1,T(m,n-1)+1,\\T(m-1,n-1)+diff(m,n)\} $$

这样就把表填完了