BDFH is a subsequence of ABCDEFGH. Given two lists, what’s the longest common subsequence? optimal substructure We consider sub problems’ of finding LCS of prefixes C[i,j]. Casework: C[i,j] = … for A[i] = B[j], then C[i,j] = C[i-1, j-1] + 1 for A[i] != B[j] = max(C[i,j-1], C[i-1,j]) if i=0 or j=0, then 0 Filling this table is O\left(nm\right), and backtracing takes O\left(n+m\right).