一个序列 S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。↔ 给出最优子结构的定义、证明，递推公式，画出dp表以及最终结论。↔其中S1=BDCBABB,S2=ABECBAB。

最长公共子序列 (Longest Common Subsequence, LCS) 的问题确实涉及到了动态规划 (Dynamic Programming, DP) 的应用。最优子结构是指原问题的解可以通过其子问题的最优解推导出来，而且各个子问题之间相互独立。对于LCS问题，这个特性体现在我们只需要考虑两个序列的部分就可以找到整个序列的最长公共子序列。

**定义：**
给定两个字符串 \(S1\) 和 \(S2\)，LCS问题是求这两个字符串中最长的那个子序列，这个子序列既出现在 \(S1\) 中又出现在 \(S2\) 中，并且顺序可以任意。

**递推公式（DP状态转移方程）：**
设 \(LCS(S1[0..i], S2[0..j])\) 表示第一个 \(i+1\) 个字符的 \(S1\) 和前 \(j+1\) 个字符的 \(S2\) 的最长公共子序列长度。那么，我们可以用以下递推关系来计算它：
- 如果 \(S1[i] = S2[j]\)，则 \(LCS(S1[0..i], S2[0..j]) = LCS(S1[0..i-1], S2[0..j-1]) + 1\)，因为当前字符匹配，直接加一。
- 如果 \(S1[i] \neq S2[j]\)，则 \(LCS(S1[0..i], S2[0..j]) = max(LCS(S1[0..i-1], S2[0..j]), LCS(S1[0..i], S2[0..j-1]))\)，取不包含当前字符的最大值。

**DP表格（举例）：**
以字符串 \(S1 = BDCBABB\) 和 \(S2 = ABECBAB\) 为例，我们可以创建一个二维数组，行代表 \(S1\) 的每个字符，列代表 \(S2\) 的每个字符。例如，在第 \(i\) 行第 \(j\) 列的格子存储的是 \(S1[0...i-1]\) 和 \(S2[0...j-1]\) 的最长公共子序列长度。

   A   B   E   C   B   A   B
A 0   0   0   0   0   0   0
B 0   0   0   0   0   1   1
D 0   0   0   0   1   1   1
C 0   0   0   1   1   1   1
B 0   1   1   1   2   2   2
A 0   1   1   1   2   3   3
B 0   1   1   1   2   3   4

**最终结论：**
通过填充这个表格，最右下角的值即为 \(S1\) 和 \(S2\) 的最长公共子序列的长度。在这个例子中，\(LCS(S1, S2)\) 就是 4，对应的子序列可能是 "CBAB" 或者 "BABA"（由于顺序无关紧要）。