Edit distance from "kitten" to "sitting": the fewest inserts, deletes and replacements. Cell (i, j) is the distance between the first i letters and the first j. Turning i letters into nothing takes i deletes, and nothing into j letters takes j inserts: the edges.
Building the edit-distance table for kitten and sitting. Row 0 and column 0 are the base cases.
(1, 1): 'k' against 's'. Different letters. Replace costs 1 + diagonal 0, delete 1 + above 1, insert 1 + left 1. Cheapest: 1.
Cell 1, 1 compares k with s and becomes 1.
(1, 2): 'k' against 'i'. Different letters. Replace costs 1 + diagonal 1, delete 1 + above 2, insert 1 + left 1. Cheapest: 2.
Cell 1, 2 compares k with i and becomes 2.
(1, 3): 'k' against 't'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 3, insert 1 + left 2. Cheapest: 3.
Cell 1, 3 compares k with t and becomes 3.
(1, 4): 'k' against 't'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 4, insert 1 + left 3. Cheapest: 4.
Cell 1, 4 compares k with t and becomes 4.
(1, 5): 'k' against 'i'. Different letters. Replace costs 1 + diagonal 4, delete 1 + above 5, insert 1 + left 4. Cheapest: 5.
Cell 1, 5 compares k with i and becomes 5.
(1, 6): 'k' against 'n'. Different letters. Replace costs 1 + diagonal 5, delete 1 + above 6, insert 1 + left 5. Cheapest: 6.
Cell 1, 6 compares k with n and becomes 6.
(1, 7): 'k' against 'g'. Different letters. Replace costs 1 + diagonal 6, delete 1 + above 7, insert 1 + left 6. Cheapest: 7.
Cell 1, 7 compares k with g and becomes 7.
(2, 1): 'i' against 's'. Different letters. Replace costs 1 + diagonal 1, delete 1 + above 1, insert 1 + left 2. Cheapest: 2.
Cell 2, 1 compares i with s and becomes 2.
(2, 2): 'i' against 'i'. Same letter, nothing to pay: copy the diagonal, 1.
Cell 2, 2 compares i with i and becomes 1.
(2, 3): 'i' against 't'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 3, insert 1 + left 1. Cheapest: 2.
Cell 2, 3 compares i with t and becomes 2.
(2, 4): 'i' against 't'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 4, insert 1 + left 2. Cheapest: 3.
Cell 2, 4 compares i with t and becomes 3.
(2, 5): 'i' against 'i'. Same letter, nothing to pay: copy the diagonal, 4.
Cell 2, 5 compares i with i and becomes 4.
(2, 6): 'i' against 'n'. Different letters. Replace costs 1 + diagonal 5, delete 1 + above 6, insert 1 + left 4. Cheapest: 5.
Cell 2, 6 compares i with n and becomes 5.
(2, 7): 'i' against 'g'. Different letters. Replace costs 1 + diagonal 6, delete 1 + above 7, insert 1 + left 5. Cheapest: 6.
Cell 2, 7 compares i with g and becomes 6.
(3, 1): 't' against 's'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 2, insert 1 + left 3. Cheapest: 3.
Cell 3, 1 compares t with s and becomes 3.
(3, 2): 't' against 'i'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 1, insert 1 + left 3. Cheapest: 2.
Cell 3, 2 compares t with i and becomes 2.
(3, 3): 't' against 't'. Same letter, nothing to pay: copy the diagonal, 1.
Cell 3, 3 compares t with t and becomes 1.
(3, 4): 't' against 't'. Same letter, nothing to pay: copy the diagonal, 2.
Cell 3, 4 compares t with t and becomes 2.
(3, 5): 't' against 'i'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 4, insert 1 + left 2. Cheapest: 3.
Cell 3, 5 compares t with i and becomes 3.
(3, 6): 't' against 'n'. Different letters. Replace costs 1 + diagonal 4, delete 1 + above 5, insert 1 + left 3. Cheapest: 4.
Cell 3, 6 compares t with n and becomes 4.
(3, 7): 't' against 'g'. Different letters. Replace costs 1 + diagonal 5, delete 1 + above 6, insert 1 + left 4. Cheapest: 5.
Cell 3, 7 compares t with g and becomes 5.
(4, 1): 't' against 's'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 3, insert 1 + left 4. Cheapest: 4.
Cell 4, 1 compares t with s and becomes 4.
(4, 2): 't' against 'i'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 2, insert 1 + left 4. Cheapest: 3.
Cell 4, 2 compares t with i and becomes 3.
(4, 3): 't' against 't'. Same letter, nothing to pay: copy the diagonal, 2.
Cell 4, 3 compares t with t and becomes 2.
(4, 4): 't' against 't'. Same letter, nothing to pay: copy the diagonal, 1.
Cell 4, 4 compares t with t and becomes 1.
(4, 5): 't' against 'i'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 3, insert 1 + left 1. Cheapest: 2.
Cell 4, 5 compares t with i and becomes 2.
(4, 6): 't' against 'n'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 4, insert 1 + left 2. Cheapest: 3.
Cell 4, 6 compares t with n and becomes 3.
(4, 7): 't' against 'g'. Different letters. Replace costs 1 + diagonal 4, delete 1 + above 5, insert 1 + left 3. Cheapest: 4.
Cell 4, 7 compares t with g and becomes 4.
(5, 1): 'e' against 's'. Different letters. Replace costs 1 + diagonal 4, delete 1 + above 4, insert 1 + left 5. Cheapest: 5.
Cell 5, 1 compares e with s and becomes 5.
(5, 2): 'e' against 'i'. Different letters. Replace costs 1 + diagonal 4, delete 1 + above 3, insert 1 + left 5. Cheapest: 4.
Cell 5, 2 compares e with i and becomes 4.
(5, 3): 'e' against 't'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 2, insert 1 + left 4. Cheapest: 3.
Cell 5, 3 compares e with t and becomes 3.
(5, 4): 'e' against 't'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 1, insert 1 + left 3. Cheapest: 2.
Cell 5, 4 compares e with t and becomes 2.
(5, 5): 'e' against 'i'. Different letters. Replace costs 1 + diagonal 1, delete 1 + above 2, insert 1 + left 2. Cheapest: 2.
Cell 5, 5 compares e with i and becomes 2.
(5, 6): 'e' against 'n'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 3, insert 1 + left 2. Cheapest: 3.
Cell 5, 6 compares e with n and becomes 3.
(5, 7): 'e' against 'g'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 4, insert 1 + left 3. Cheapest: 4.
Cell 5, 7 compares e with g and becomes 4.
(6, 1): 'n' against 's'. Different letters. Replace costs 1 + diagonal 5, delete 1 + above 5, insert 1 + left 6. Cheapest: 6.
Cell 6, 1 compares n with s and becomes 6.
(6, 2): 'n' against 'i'. Different letters. Replace costs 1 + diagonal 5, delete 1 + above 4, insert 1 + left 6. Cheapest: 5.
Cell 6, 2 compares n with i and becomes 5.
(6, 3): 'n' against 't'. Different letters. Replace costs 1 + diagonal 4, delete 1 + above 3, insert 1 + left 5. Cheapest: 4.
Cell 6, 3 compares n with t and becomes 4.
(6, 4): 'n' against 't'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 2, insert 1 + left 4. Cheapest: 3.
Cell 6, 4 compares n with t and becomes 3.
(6, 5): 'n' against 'i'. Different letters. Replace costs 1 + diagonal 2, delete 1 + above 2, insert 1 + left 3. Cheapest: 3.
Cell 6, 5 compares n with i and becomes 3.
(6, 6): 'n' against 'n'. Same letter, nothing to pay: copy the diagonal, 2.
Cell 6, 6 compares n with n and becomes 2.
(6, 7): 'n' against 'g'. Different letters. Replace costs 1 + diagonal 3, delete 1 + above 4, insert 1 + left 2. Cheapest: 3.
Cell 6, 7 compares n with g and becomes 3.
Edit distance 3, the bottom-right cell. 56 cells, each from three neighbours: O(m x n).
The answer is 3.