最长公共子序列的变种：带通配符和间隔限制的最长公共子序列（允许通配符匹配任意字符，且匹配字符之间允许最多跳过k个字符）

1. 题目描述

给定两个字符串 s 和 t，以及一个非负整数 k。
定义一种带通配符和间隔限制的匹配规则：

• 字符串 s 和 t 中可以包含通配符 '?'，它可以匹配任意字符（包括字母、数字等，也包括另一个通配符）。
• 在匹配时，允许在 s 和 t 中跳过字符，但要求跳过的字符总数（在 s 和 t 中跳过的字符数之和）不超过 k。

要求找出最长公共子序列（LCS），使得这个子序列是满足上述规则的最长序列。
注意：子序列的定义是原字符串中顺序相同但不必连续的一组字符。

2. 问题理解与举例

假设：

• s = "a?b"
• t = "acb"
• k = 1

解释：

• 通配符 '?' 可以匹配任意字符。
• 跳过字符的总数 ≤ 1。

一种可能的匹配：

• 在 s 中取 'a'，在 t 中取 'a' → 匹配，跳过字符数 = 0。
• 在 s 中取 '?'，在 t 中取 'c' → 通配符匹配成功，跳过字符数不变。
• 在 s 中取 'b'，在 t 中取 'b' → 匹配，跳过字符数不变。

最终子序列为 "acb"，长度为 3。
注意：这里没有跳过任何字符，跳过的字符总数 = 0 ≤ 1，满足条件。
输出结果应为 3。

3. 状态定义

这是一个线性动态规划问题，我们需要记录三个维度：

• i: 表示在字符串 s 中考虑前 i 个字符（1 ≤ i ≤ len(s)）。
• j: 表示在字符串 t 中考虑前 j 个字符（1 ≤ j ≤ len(t)）。
• skip: 表示到目前为止，在匹配过程中总共跳过的字符数（0 ≤ skip ≤ k）。

定义 dp[i][j][skip] 表示：
考虑 s 的前 i 个字符和 t 的前 j 个字符，且累计跳过字符数为 skip 时，能够匹配的最长子序列的长度。

初始值：

• 当 i = 0 或 j = 0 时，表示一个字符串为空，此时最长公共子序列长度为 0，跳过字符数 = 当前已跳过的字符数（即跳过另一个字符串的所有字符）。
  实际上，初始化时会根据 skip 的取值来处理，但我们可以从状态转移中自然推导。

4. 状态转移方程

对于状态 (i, j, skip)，有四种情况：

情况 1：匹配 s[i-1] 和 t[j-1]（末尾字符可匹配）

匹配的条件是：

• s[i-1] == t[j-1] 或 s[i-1] == '?' 或 t[j-1] == '?'。

如果匹配，则我们可以将这两个字符纳入子序列，此时子序列长度 +1，且跳过字符数不变（因为两个字符都用了，没有跳过任何字符）：

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

前提是 skip 相同，因为不增加跳过数。

情况 2：跳过 s[i-1]（不将 s[i-1] 纳入子序列）

这意味着我们在 s 中跳过一个字符，跳过字符数 +1，但 j 保持不变（因为 t 当前位置未处理）。
因此，状态转移为：

if skip > 0:
    dp[i][j][skip] = max(dp[i][j][skip], dp[i-1][j][skip-1])

注意：这里 skip-1 是因为我们现在要消耗一次跳过机会。

情况 3：跳过 t[j-1]（不将 t[j-1] 纳入子序列）

类似地，在 t 中跳过一个字符：

if skip > 0:
    dp[i][j][skip] = max(dp[i][j][skip], dp[i][j-1][skip-1])

情况 4：同时跳过 s[i-1] 和 t[j-1]

这种情况其实等价于先跳 s 再跳 t（或反之），但会消耗 2 次跳过机会。
所以需要 skip ≥ 2：

if skip ≥ 2:
    dp[i][j][skip] = max(dp[i][j][skip], dp[i-1][j-1][skip-2])

不过，这种情况可以被“先跳 s 再跳 t”的两次转移覆盖，所以可以省略，但为了清晰可以保留。

5. 初始化和边界

• 当 i = 0 时，表示 s 为空，为了匹配到 t 的前 j 个字符，我们必须跳过 t 的所有 j 个字符。
  所以 dp[0][j][skip] 只有当 skip ≥ j 时才可能为 0，否则为无效状态（用 -∞ 表示）。
• 同理，dp[i][0][skip] 只有当 skip ≥ i 时才为 0。
• 我们可以将整个 dp 数组初始化为 -∞（或一个很小的负数），表示不可达状态，然后设置 dp[0][0][0] = 0 作为起点。
• 在计算时，我们只从有效状态转移。

6. 计算顺序与答案

计算顺序：

for i in [0..len(s)]:
    for j in [0..len(t)]:
        for skip in [0..k]:
            // 根据上述状态转移计算 dp[i][j][skip]

注意：当 i=0 或 j=0 时，跳过字符数必须足够才能转移到当前状态。

最终答案：
在 dp[len(s)][len(t)][skip] 中，skip 从 0 到 k 的最大值，即为所求。

7. 示例推导（手动推一小段）

以 s = "a?b", t = "acb", k = 1 为例。

设 s 长度 m=3, t 长度 n=3, k=1。
初始化 dp[0][0][0]=0，其他为 -∞。

i=1, j=1（比较 s[0]='a', t[0]='a'）：
匹配：dp[1][1][0] = dp[0][0][0] + 1 = 1。
跳过 s[0]：需要 skip≥1，dp[1][1][1] = dp[0][1][0] 但 dp[0][1][0] 无效（因为跳过 t[0] 需要 skip≥1，所以 dp[0][1][0] 为 -∞）。
跳过 t[0]：类似，无效。

逐步计算到 i=3, j=3 后，
dp[3][3][0] 会得到 3（路径是匹配所有三个字符）。

验证：跳过字符数=0，满足 k=1，所以答案为 3。

8. 时间复杂度与空间优化

• 时间复杂度：O(m * n * k)，其中 m, n 为字符串长度。
• 空间复杂度：可优化为 O(n * k) 的滚动数组，因为 dp[i] 只依赖于 dp[i-1]。

9. 核心要点总结

1. 本题是 LCS 的扩展，引入了通配符匹配和总跳过字符数限制。
2. 状态设计需要额外一维记录已跳过字符数。
3. 转移时考虑匹配、跳过一个字符、跳过两个字符等情况。
4. 注意初始化时跳过字符数与字符串长度的关系。

掌握这个模型后，可以处理更复杂的带跳过限制的序列匹配问题。