{\(D(x(1..i−1),y(1..j−1))+\) 1 {if \(x\left(i\right)\ne y\left(j\right)\)
0 {if \(x\left(i\right)=y\left(j\right)\)
eg.
- kitten → sitten (substitution of "s" for "k")
- sitten → sittin (substitution of "i" for "e")
- sittin → sitting (insertion of "g" at the end).
Cost=1+1+1=3