我正在经历 CLRS 的算法简介中最长的常见子序列问题。但我无法理解其背后的思考过程。解释的大多数其他问题都非常直观，并且我相信我将来可以解决类似的问题，但我无法可视化 LCS 问题，因为我不了解如何确定最佳子结构背后的逻辑。
该书对最佳子结构进行了以下解释
**定理 15.1（LCS 的最优子结构）
令 X == 和 Y == 是序列，令 Z = 是 X 和 Y 的任意 LCS。 1. 如果xm = yn，则zk = xm = yn和Zk−1是 和 的Xm−1LCS Yn−1。2. 如果xm != yn,thenzk = xm意味着是和Z的 LCS 。3. 如果,then意味着是和的 LCS 。证明 (1) 如果，那么我们可以追加以获得 和 的公共子序列，这与作为和的最长公共子序列的假设相矛盾。因此，我们必须有.Xm−1Yxm != ynzk = ynZXYn−1zk != xmxm = ynZXYk + 1ZXYzk = xm = yn
现在，前缀Zk−1是and的length-(k − 1)公共子序列。我们希望证明它是 LCS。为了矛盾的目的，假设存在 和 的公共子序列，其长度大于。然后，追加to会产生 的公共子序列，其
长度大于，这是矛盾的。Xm−1Yn−1WXm−1Yn−1k−1xm = ynWXYk
(2) If zk != xm,thenZ是Xm−1and的公共子序列Y。如果and的公共子序列长度大于，那么也将是 and 的公共子序列，W这与 and的
LCS的假设相矛盾。Xm−1YkWXmYZXY
(3) 证明与 (2) 对称。**
证据很清楚，但我看不出他们是如何提出最佳子结构的。有人可以帮忙吗？