Help understanding edit distance for pset6 similarities

Question

I get the basic gist of edit distance, but there's a part in one of the walkthrough videos for pset6/similarities which I don't understand.

https://www.youtube.com/watch?list=PLhQjrBD2T381-bOArPXzvlXpovpdBhrZ3&time_continue=367&v=YTO92oVoYwA

At 6:08:

He's trying to figure out the edit distance from converting 'C' to 'A'. First he looks one square from the top (i.e. going from ' ' to 'A') which is 1,I.

Then using 1,I he computes 'C' to 'A' with 2,D.

But question is, how is the last operation a D?

If you go from ' ' to 'A', which is 1,I, and then 'A' to 'C', then wouldn't the computation be 2,S with the last operation being a substituion (of 'A' into 'C') instead of a deletion?

Please help me understand how this is a deletion instead of a substitution.

Answer 1

There are three ways to get there: 2,D (cat->acat->aat), 2,I (cat->at->aat), 1,S (cat->aat) (a substitution here costs the same as an insertion or deletion, but it's relative to the left upper neighbour, with the upper left corner having an associated cost of 0).

A substitution advances both indices at once, in the source and in the target.

The algorithm will compare all three (and in the video, all three are shown), and keep the one with the lowest cost associated, here 1,S.