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) ?
1 Answers
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.
Related