Okay, so assume for the time being that it is an insertion.

Then what we know for sure is that is has a last symbol of the last character of B

that is inserted, which means that in this column, we have a gap at the top.

And we have the last element of B at the bottom, okay?

Now let's consider what happens if we cut this last column out of this alignment.

Then what is left must be an alignment of the word A with

the prefix of lengths n- 1 of the word B.

And what is more, this alignment must be optimal.

Why is it?

Well begin by the cut and paste tree.

Because if this alignment, if this sum alignment is not optimal,

meaning that there is some other less expensive alignment.

Then we can cut this initial alignment and

replace it by less expensive alignment here, okay?

So another possibility is that the last column is a deletion.

Then, what we know is that in this case, we delete the last symbol of A.

And what is left if we cut the last column,

must be an optimal alignment of the prefix of A, and the word B.

And the last possibility is that if in the last column, we have two letters,

then what we know is that if we cut this column, then what is left must be

again an optimal alignment of the prefix of lengths n- 1 of the word E.

And the prefix of the lengths m- 1 of the word B, okay?

This suggests that we define our subproblems as follows.

Let's define ED(i,j) as the least expensive alignment or just the cost

of the least expensive alignment of the prefix of lengths i of the word A.

And the prefix of length j of the word B.

Then, our previous analysis,

shows that we can compute ED(i,j) as follows.

So this alignment for prefixes is again,

its last column is either an insertion, a deletion or a match or mismatch.

Recall that we pay 1 for insertions, for deletions, and for mismatches.

And we pay nothing for matches.

Okay, this allows us to write the following recurrence relations for

ED(i,j).

ED(i,j) is equal to minimum of ED(i-1,

j) +1 or ED(i, j-1) +1 or

ED(i-1, j-1) + the difference

between the i symbol of A and the j symbol of B.

And by this difference, we mean the following simple function.

If it is equal to 1, if the corresponding two symbols are different.

And it is equal to 0 if they are the same.

This basically corresponds to the fact that we pay 1 for

different symbols or for mismatches.

And we pay 0 or nothing for matches, okay?

So the base case for this recurrence relation is the following.

When i = 0, ED(i,j) = j.

And similarly, when j = 0, then ED(i,j) = i.

Why is that?

Well in this case we just tried to find an optimal alignment of

an empty prefix of some worth and with some, possibly none empty.

A prefix of some other word.

In this case, obviously, an optimal way of getting one prefix

from the empty prefix or getting the empty prefix from some other

is either the insert all the elements or delete all the elements.

And in this case we need exactly i or j operations, okay.

So once again, when we have a recurrence relation,

it is just a technicality to transform it into recursive algorithm.

So for this, we just introduced, we just initialize the table.

And then each time when we make a recursive call, we first check with

the the solution for the corresponding subproblem (i,j) is already in the table.

And if it is in the table, we immediately return the result.

If it is not in the table, we compute its value by making three recursive calls.

Or if it is just a base case we compute it in a straightforward way.

And when we compute it, we save it through the table, in order to avoid

recomputing the solution for the same subproblem again, okay?

Now our goal is to convert this recursive algorithm into an iterative algorithm.

So recall that the space of all our subproblems is all the values of (i,j),

where i and j range from 0 to n and m respectively.

This suggests actually that we can use just the 2D table for

storing all the solutions for our subproblems.

And this is what we're going to do.