0
我正在經歷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）。**
證明是明確的，但我看不出他們是如何想出了最優子。 有人可以幫忙嗎？