最优子结构性质

Question

假设我们有两个字符串X，Y，长度分别为n，m。我找到了X和Y的最长公共子序列Z。

如何证明最长公共子序列(LCS)的最优子结构性质？

Answer 1

为了证明问题的子结构是最优的，您需要首先定义state是什么。

LCS问题：

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

定义国家/地区

对于LCS问题，让我们将状态D[i,j]定义为：

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]**

提出递归关系(Di，j)：

案例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])

案例2：

x[i] != y[j]

Argument follows directly from previous case:

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

最优的推理来自归纳，因为我们自下而上地构建最终答案D[N,M]。