最长公共子序列的变种：带字符必须按顺序出现限制的最长公共子序列（进阶版：限制某些字符必须按序出现，并且这些字符之间可以有间隔，但顺序必须严格保持）

题目描述
给定两个字符串 s 和 t，以及一个模式字符串 pattern。我们需要找到 s 和 t 的最长公共子序列（LCS），但这个公共子序列必须满足一个额外条件：它必须以 pattern 中字符的顺序出现（即 pattern 必须是这个公共子序列的一个子序列，可以不连续，但顺序必须一致）。注意，pattern 中的字符不一定要在公共子序列中连续出现，只要顺序保持即可。而且，pattern 中的字符可能在公共子序列中出现多次，只要保持顺序即可。但更常见且明确的题意是：找到 s 和 t 的一个公共子序列，使得 pattern 是该公共子序列的一个子序列。求这个满足条件的公共子序列的最大长度。

示例
s = "abcde"
t = "acebde"
pattern = "ace"
满足条件的公共子序列可以是 "ace"（s 的子序列 "a"、"c"、"e"，t 的子序列 "a"、"c"、"e"），长度为 3。
另一个可能的公共子序列是 "acde"（s 的子序列 "a"、"c"、"d"、"e"，t 的子序列 "a"、"c"、"d"、"e"），它包含 "a"、"c"、"e" 按顺序，所以也满足条件，长度为 4。
但 "abde" 虽然也是公共子序列，但它不包含 "c"，所以不满足 pattern 按序出现的要求。
因此答案是 4。

解题思路
这是一个带限制的 LCS 问题。我们可以将原问题转化为三维动态规划，状态定义为：dp[i][j][k] 表示考虑 s 的前 i 个字符、t 的前 j 个字符，并且已经匹配了 pattern 的前 k 个字符（即当前公共子序列中已经按顺序包含了 pattern[0..k-1]）的情况下，满足条件的最长公共子序列的长度。

状态转移：

1. 当 s[i-1] == t[j-1] 时，我们考虑是否将当前相同字符加入公共子序列。
   • 如果加入，那么这个字符可能会对 pattern 的匹配产生影响：
     • 如果当前字符等于 pattern[k]，那么它可以作为 pattern 的第 k+1 个匹配字符，于是 k 可以增加 1。
     • 否则，k 保持不变。
       所以转移为：

     dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k'] + 1)
     其中 k' 是加入前已匹配的 pattern 字符数。具体地：
       如果 s[i-1] == pattern[k-1] (注意 pattern 下标从0开始，k 表示已匹配的个数，所以下一个待匹配的是 pattern[k])，
       则 k' = k-1 （即匹配前已匹配了 k-1 个，当前字符匹配了第 k 个）
       否则 k' = k （已匹配个数不变）。
     

   • 如果不加入这个字符，那么可以跳过 s[i-1] 或 t[j-1]，这会在其他转移中覆盖。
2. 当 s[i-1] != t[j-1] 时，我们不能同时取两个字符，只能跳过其中一个：

   dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k])
   

3. 边界条件：dp[0][j][0] = 0, dp[i][0][0] = 0，其他为 -∞（表示不可行），因为若尚未匹配任何 pattern 字符，k 必须为 0。

但注意：我们要求公共子序列必须包含 pattern 作为子序列，所以最终答案应该是 dp[n][m][K]，其中 K 是 pattern 的长度，表示 pattern 完全匹配。

详细步骤：

1. 设 n = len(s), m = len(t), K = len(pattern)。
2. 初始化三维数组 dp[n+1][m+1][K+1]，全部填充为 -INF（表示不可行）。
3. 初始化基础状态：对于所有 i, j，dp[i][j][0] = 0，因为不要求匹配任何 pattern 字符时，长度为 0 总是可行的。
4. 状态转移：

   for i in 1..n:
     for j in 1..m:
       for k in 0..K:
          # 不取 s[i-1] 或 t[j-1]
          dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k])
          if s[i-1] == t[j-1]:
             ch = s[i-1]
             if k > 0 and ch == pattern[k-1]:
                # 当前字符匹配 pattern 的第 k 个字符
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + 1)
             # 当前字符不用于匹配 pattern（但仍是公共子序列的一部分）
             # 注意：只有当 pattern 的匹配状态不变时才可以
             dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1)
   

5. 最终答案：dp[n][m][K]。如果它为负数，说明没有这样的公共子序列，返回 0 或 -1（根据题目要求）。否则返回该值。

复杂度：O(n * m * K)，空间可通过滚动数组优化到 O(m * K)。

举例验证（用上面的例子）：
s = "abcde", t = "acebde", pattern = "ace"
n=5, m=6, K=3
逐步计算后，dp[5][6][3] 应该为 4，对应公共子序列 "acde"。

思考：为什么上面的转移中，当字符相同且不用于匹配 pattern 时，我们允许从 dp[i-1][j-1][k] + 1 转移？因为该字符可以加入公共子序列，但不作为 pattern 的匹配部分，所以已匹配的 pattern 字符数 k 不变。

注意事项：

• 如果 pattern 为空，则问题退化为普通 LCS，答案为 dp[n][m][0]，即普通 LCS 长度。
• 该算法可扩展到 pattern 中有重复字符的情况，因为转移时我们只关心匹配个数，不关心具体位置。

这个算法能正确处理必须按顺序包含 pattern 的限制，同时最大化公共子序列长度。