DP Table — Longest Common Subsequence (Section 2.2)

Recurrence (Equation 1):

c[i,j] = 0 if i = 0 or j = 0
c[i,j] = c[i-1,j-1] + 1 if i,j > 0 and X[i] = Y[j]
c[i,j] = max(c[i,j-1], c[i-1,j]) if i,j > 0 and X[i] ≠ Y[j]

Each cell depends on its upper, left, and diagonal neighbors. The orange path is the trace-back chain that gives the LCS. Cells with an orange border are matches (X[i] = Y[j]).

X (read, ≤ 6): Y (reference, ≤ 10):

Boundary (= 0) Interior cell Match (X[i] = Y[j]) Trace-back path