The LCS recurrence (type it)

Answer

c[i,j] = 0 if i = 0 or j = 0 c[i,j] = c[i-1,j-1] + 1 if x_i = y_j c[i,j] = max(c[i-1,j], c[i,j-1]) if x_i != y_j

Three exhaustive cases: empty prefix → 0, matched last chars → extend the diagonal, mismatch → take the better of dropping one element from either string.