# DP for Minimum Edit Distance

## Problem

Calculate the minimum edit distance of the two sequences, $x_{1\ldots m} = x_1 \ldots x_m$ and $y_{1\ldots n} = y_1 \ldots y_n$

## Definition

$D_{i,j}$ is the minimum edit distance of the (sub)sequences $x_{1…i} = x_1 \ldots x_i$ and $y_{1\ldots j} = y_1 \ldots y_j$

## Initialization

$D_{0,0} = 0 \\ D_{i,0} = i \mbox{ for } i=1, \ldots m \\ D_{0,j} = j \mbox{ for } j=1, \ldots n \\$

## Iteration

$\mbox{ for } i=1, \ldots m\\ \mbox{ for } j=1, \ldots n\\ D_{i,j}= \min \left[ \begin{array}{l} D_{i-1,j-1} + \delta(a_i,b_j), \\ D_{i-1,j} +1, \\ D_{i,j-1} +1 \end{array} \right.$
where
$\delta(a_i,b_j) = [ a_i == b_j ? 0:1 ]$