Longest common subsequence of "abcde" and "ace". Cell (i, j) is the answer for the first i letters of one against the first j of the other. Row 0 and column 0 are empty prefixes, so they hold 0.
Building the lcs table for abcde and ace. Row 0 and column 0 are the base cases.
(1, 1): 'a' against 'a'. They match, so both prefixes end in a shared letter: diagonal 0 + 1 = 1.
Cell 1, 1 compares a with a and becomes 1.
(1, 2): 'a' against 'c'. Different letters. Drop one from either side: max(above 0, left 1) = 1.
Cell 1, 2 compares a with c and becomes 1.
(1, 3): 'a' against 'e'. Different letters. Drop one from either side: max(above 0, left 1) = 1.
Cell 1, 3 compares a with e and becomes 1.
(2, 1): 'b' against 'a'. Different letters. Drop one from either side: max(above 1, left 0) = 1.
Cell 2, 1 compares b with a and becomes 1.
(2, 2): 'b' against 'c'. Different letters. Drop one from either side: max(above 1, left 1) = 1.
Cell 2, 2 compares b with c and becomes 1.
(2, 3): 'b' against 'e'. Different letters. Drop one from either side: max(above 1, left 1) = 1.
Cell 2, 3 compares b with e and becomes 1.
(3, 1): 'c' against 'a'. Different letters. Drop one from either side: max(above 1, left 0) = 1.
Cell 3, 1 compares c with a and becomes 1.
(3, 2): 'c' against 'c'. They match, so both prefixes end in a shared letter: diagonal 1 + 1 = 2.
Cell 3, 2 compares c with c and becomes 2.
(3, 3): 'c' against 'e'. Different letters. Drop one from either side: max(above 1, left 2) = 2.
Cell 3, 3 compares c with e and becomes 2.
(4, 1): 'd' against 'a'. Different letters. Drop one from either side: max(above 1, left 0) = 1.
Cell 4, 1 compares d with a and becomes 1.
(4, 2): 'd' against 'c'. Different letters. Drop one from either side: max(above 2, left 1) = 2.
Cell 4, 2 compares d with c and becomes 2.
(4, 3): 'd' against 'e'. Different letters. Drop one from either side: max(above 2, left 2) = 2.
Cell 4, 3 compares d with e and becomes 2.
(5, 1): 'e' against 'a'. Different letters. Drop one from either side: max(above 1, left 0) = 1.
Cell 5, 1 compares e with a and becomes 1.
(5, 2): 'e' against 'c'. Different letters. Drop one from either side: max(above 2, left 1) = 2.
Cell 5, 2 compares e with c and becomes 2.
(5, 3): 'e' against 'e'. They match, so both prefixes end in a shared letter: diagonal 2 + 1 = 3.
Cell 5, 3 compares e with e and becomes 3.
The longest common subsequence has length 3, the bottom-right cell. 24 cells, each from three neighbours: O(m x n).
The answer is 3.