Optimal Substructure Property

Question

suppose we have two Strings X,Y of length n,m respectively. I found the longest common subsequence Z of X and Y.

how can I prove the optimal substructure property of the longest common subsequence (LCS) ?

Answer 1

To prove for optimality in the substructures of the problem, you need to first start with defining what your state is.

LCS problem:

Strings: X, Y
X = x1x2.....xN #length=N
Y = y1y2.....yM #length=M

Define States

For LCS problem, lets define our state D[i,j] as:

D[i,j] = longest common subsequence of substrings X[1:i] and Y[1:j]

Based on our definition above, we are looking to find the value of **D[N, M]**

Come up with recurrence-relation (D[i,j]):

Case 1:

x[i] == y[j] 

1. If the characters we are comparing are already the same, it can very well be part of the longest-common-subsequence for X[1:i] and Y[1:j].
2. The LCS might also turn-out from X[1:i-1] & Y[1:j]; OR
3. turn-out from X[1:i] & Y[1:j-1]

Thus,
D[i][j] = maxlen(D[i-1][j-1] + {X[i]}, D[i-1][j], D[i][j-1])

Case 2:

x[i] != y[j]

Argument follows directly from previous case:

D[i][j] = maxlen(D[i-1][j], D[i][j-1])

The reasoning for optimality follows from Induction since we build the final-answer D[N,M] from bottom-to-top.