Optimal Substructure Theorem

Let $X = \langle x_1, x_2, \ldots, x_m\rangle$ and $Y=\langle y_1,y_2,\ldots,y_n\rangle$ be sequences, and let $Z=\langle z_1,z_2,\ldots,z_k\rangle$ be any LCS of X and Y.

• 1. If x_m = y_n, then z_k = x_m = y_n and Z_k-1 is an LCS of X_m-1 and Y_n-1.
• 2. If $x_m \neq y_n$, then $z_k \neq x_m$ implies that Z is an LCS of X_m-1 and Y.
• 3. If $x_m \neq y_n$, then $z_k \neq y_n$ implies that Z is an LCS of X and Y_n-1.