最长的公共子序列算法
我正在经历CLRS中最简单的子序列问题，但我无法理解它背后的思想过程。大部分解释的其他问题都非常直观，我相信我可以在将来解决类似问题，但我无法想象LCS问题，因为我不了解最佳子结构如何确定背后的逻辑。最长的公共子序列算法
书中给出的最佳子结构
**定理15.1（的LCS的最优子）
设X ==和Y ==是序列，并且让Z = 在以下的说明是X和Y的任何LCS。 1.如果xm = yn，则zk = xm = yn和Zk−1是LBS Xm−1和Yn−1。 2.如果是xm != yn，那么zk = xm意味着Z是Xm−1和Y的LCS。 3.如果xm != yn，则zk = yn意味着Z是X和Yn−1的LCS。 证明（1）如果zk != xm，那么我们就可以追加xm = yn到Z以获得共同 子序列的X和长度k + 1的Y，矛盾的假设上Z是 的X和Y一个最长公共子序列。因此，我们必须有zk = xm = yn。
现在，前缀Zk−1是Xm−1和Yn−1的length-(k − 1)共同子序列。 我们希望证明它是一个LCS。假设出于矛盾的目的， 存在长度大于k−1的Xm−1和Yn−1的共同子序列W。 然后，追加xm = yn到W产生一个公共子序列X和Y 其长度大于k，这是一个矛盾。 （2）如果zk != xm，那么Z是Xm−1和Y的常见子序列。如果有一个 公共子序列Xm−1W和Y长度大于k大，那么将W也 是Xm和Y一个公共子序列，矛盾的假设是Z 是X和Y的LCS。
（3）证明是对称的（2）。**
证明是明确的，但我看不出他们是如何想出了最优子。 有人可以帮忙吗？
请通过下面的链接复发部分：
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined
这些递推关系不过是最优子结构和重叠子问题等式。