Edit distance ($D[i,j]$)

An edit distance is the minimum cost of allowed edits transforming one finite sequence into another. With unit insertion, deletion and substitution costs, the prefix table has boundaries $D[i,0]=i$, $D[0,j]=j$ and recurrence $D[i,j]=\min (D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+[x_i\ne y_j])$. The last alignment action gives one of these cases; appending that action to an optimal shorter alignment proves the converse inequality. Thus induction proves the recurrence, yielding $O(mn)$ running time for nonempty input lengths $m,n$. Two rolling rows suffice when only the distance is required; retaining predecessor actions supports reconstruction.