Cost of conversion of string $A$ to string $B$

Question

We are given $2$ strings $A=[1 \dots m]$ and $B[1 \dots n]$ and the following $3$ operations are allowed:

• Insert a charachter,with cost $c_i$
• Delete a character,with cost $c_d$
• Replace a character,with cost $c_r$

We are looking for the optimal sequence of operations(sequence of operations with the minimum cost),for the conversion of the string $A$ to the string $B$.

$$T(i,j)=\text{ the minimum cost of the conversion of the string }\\ A[1 \dots i] \text{ to } B[1 \dots j], 1 \leq i \leq m, 1 \leq j \leq n$$

According to my notes: $$T(i,j)=\min \left\{\begin{matrix} T(i-1,j)+c_d & \text{ // delete the i-th charachter of A}\\ T(i,j-1)+c_i & \text{ // insert the j-th charachter of B} \\ T(i-1,j-1) & \text{if } A[i]=B[j]\\ T(i-1,j-1)+c_r & \text{if } A[i] \neq B[j] \end{matrix}\right.$$

Why is the cost given by the above formula?Could you explain it to me?

EDIT:

For example,suppose that we want to convert the string $ \text{ exponential}$ to the string $\text{ polynomial }$ ,knowing the costs:

$$ c_d=c_i=2 , c_r=1$$

I created the following matrix:

Is it right? If so,is the minimum cost of the conversion then $ T[11,10]=11$ ? Or am I wrong?

Answer 1

I'm not sure if this is what you're looking for. I'll just walk you through each of the cases. Here are possible ways to obtain a conversion from $A[1..i]$ to $B[1..j]$.

1. If you already know how to convert $A[1..(i-1)]$ to $B[1..j]$, you can convert $A[1..i]$ to $B[1..j]$ by doing what you did with $A[1..(i-1)]$, and deleting $A[i]$.
2. If you already know how to convert $A[1..i]$ to $B[1..(j-1)]$, you can convert $A[1..i]$ to $B[1..j]$ by doing what you did with $A[1..i]$, and adding $B[j]$.
3. If you already know how to convert $A[1..(i-1)]$ to $B[1..(j-1)]$, you can do what you did to $A[1..(i-1)]$, and replace $A[i]$ by $B[j]$. However, if $A[i]$ and $B[j]$ are already equal, there's no need to replace it.

One important property of this problem is that these exhaust all the possibilities. (It's quite tedious to prove this formally and I don't think people do that.) So in order to obtain $T(i, j)$, the minimum cost for converting $A[1..i]$ to $B[1..j]$, you only need to compare the costs of the three ways of obtaining the conversion, assuming that you already know minimum costs of converting smaller problems.