LCS 的最优子结构 证明

（LCS 的最优子结构）定理：令 $X= \langle x_{1},x_{2} \dots x_{m} \rangle$ 和 $Y= \langle y_{1},y_{2} \dots y_{n} \rangle$ 为两个序列，$Z= \langle z_{1},z_{2} \dots z_{k} \rangle$ 为 $X$ 和 $Y$ 的任意 LCS​。

• 如果 $x_{m}=y_{n}$，那么 $z_{k}=x_{m}=y_{n}$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个 LCS​。
• 如果 $x_{m} \neq y_{n}$，那么 $z_{k} \neq x_{m}$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个 LCS​。
• 如果 $x_{m} \neq y_{n}$，那么 $z_{k} \neq y_{n}$ 意味着 $Z$ 是 $Y_{n-1}$ 和 $X$ 的一个 LCS​。

证明：

• 如果 $z_{k} \neq x_{m}$，那么可以将 $x_{m}$ 和 $y_{n}$ 添加到 $Z$ 的末尾，得到 $X$ 和 $Y$ 是一个长度为 $k+1$ 的子序列，与 $Z$ 是 $X$ 和 $Y$ 的最长公共子序列的假设矛盾。因此必然有 $z_{k}=x_{m}=y_{n}$。这样前缀 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$的公共子序列，我们希望他是一个 LCS。利用反证法，假设存在 $X_{m-1}$ 和 $Y_{n-1}$ 的一个长度大于 $k-1$ 的公共子序列 $W$，则将 $x_{m}=y_{n}$ 追加到 $W$ 的末尾会得到一个长度大于 $k$ 的公共子序列，矛盾。
• 如果 $z_{k} \neq x_{m}$，那么 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个公共子序列。如果存在 $X_{m-1}$ 和 $Y$ 的一个长度大于 $k$ 的公共子序列 $W$，那么 $W$ 也是 $X_{m}$ 和 $Y$ 的公共子序列，与 $Z$ 是 $X$ 和 $Y$ 的最长公共子序列矛盾。
• 与情况二对称。

其递归算法具有重叠子问题的性质，为了求 $X$ 和 $Y$ 的一个 LCS，我们可能需要求 $X$ 和 $Y_{n-1}$ 的一个 LCS，但是这几个子问题都包含求解 $X_{m-1}$ 和 $Y_{n-1}$ 的 $LCS$ 的子子问题。很多其他问题也都共享子子问题。

定义 $f_{i, j}$ 表示 $X_{i}$ 和 $Y_{i}$ 的 $LCS$ 的长度。如果一个序列长度为 $0$，那么 LCS 的长度为 $0$，可以得到以下公式：
$$f_{i,j}= \begin{cases} 0 & {若i=0或j=0}\\ f_{i-1,j-1}+1 & {若i,j>0且x_{i}=y_{j}}\\ \max(f_{i,j-1},f_{i-1,j}) & {若i,j>0且x_{i} \neq y_{j}} \end{cases}$$

参考文献：算法导论（第三版）。机械工业出版社。