线性动态规划：最长公共子序列的变种——带字符跳跃限制的最长公共子序列
字数 4271 2025-12-09 08:11:19

线性动态规划：最长公共子序列的变种——带字符跳跃限制的最长公共子序列

题目描述

给定两个字符串 s1 和 s2，以及一个整数 k。
要求找到它们的最长公共子序列（LCS），但有一个额外限制：
在匹配过程中，每次跳过（不匹配）的连续字符数不能超过 k 个。

注意：

  • 我们定义“跳过”为：在匹配某一个字符串的字符时，可以跳过该字符串中的若干字符，直接匹配后面的字符。
  • 但跳过的连续字符数量不能超过 k，否则这个匹配序列无效。
  • 需要返回这个限制下最长公共子序列的长度。

示例：

s1 = "abcde"
s2 = "ace"
k = 1

正常 LCS 是 "ace"，长度 3。
这里限制 k=1，意味着在匹配过程中，如果在某个字符串中跳过字符，连续跳过不能超过 1 个。
对于这个例子，正常匹配 "a"、"c"、"e" 时，在 s1 中匹配 "a" 后，下一个匹配 "c" 需要跳过 s1 中的 'b'，只跳过 1 个字符，满足条件；匹配 "e" 时，跳过 s1 中的 'd'，也只跳过 1 个字符，满足条件，所以答案 = 3。

另一个例子：

s1 = "abcdefg"
s2 = "acfg"
k = 0

k=0 表示不允许跳过任何字符，也就是必须按顺序完全匹配 s2 在 s1 中连续出现，但这里 s2 在 s1 中不是连续的（a...c...f...g），所以无法匹配长度为 4 的序列，因为从 a 到 c 必须跳过 b，跳过了 1 个字符，违反 k=0 规则。
但我们可以匹配 "a"、"c"、"f"、"g" 吗？从 a 到 c 跳过 b（跳过 1 个字符，不允许，k=0 要求跳过数为 0），所以只有连续子串才合法。
仔细分析：k=0 时，这个“LCS 带跳跃限制”退化为寻找最长的公共子串（连续公共子序列），但注意这里是在两个字符串中都必须连续吗？不是，规则是“跳过连续字符数不超过 k”，k=0 时在两个字符串中都不能跳过任何字符，所以必须是两个字符串的公共子串（在两个字符串中都连续出现）。
我们这里先明确：跳过的定义是在单个字符串中匹配下一个字符时，跳过的该字符串的连续字符数。

逐步分析

第一步：理解“跳过”的定义

假设我们已匹配了 LCS 的某一部分，最后一个匹配的字符是 s1[i] 与 s2[j]，接下来要匹配下一个字符，需要在 s1 中找到下一个匹配位置 i' > i，在 s2 中找到 j' > j，使得 s1[i'] = s2[j']。

  • 在 s1 中，从 i+1 到 i'-1 这些字符是被跳过的，跳过的数量是 (i' - i - 1)。
  • 在 s2 中，从 j+1 到 j'-1 这些字符是被跳过的，跳过的数量是 (j' - j - 1)。

题目限制：在每个字符串中，每次匹配时跳过的连续字符数不能超过 k。
也就是说：

\[i' - i - 1 \le k \quad \text{且} \quad j' - j - 1 \le k \]

并且这两个条件必须同时满足，否则这次匹配就是无效的。

第二步：动态规划状态设计

设 dp[i][j] 表示以 s1[i] 和 s2[j] 作为 LCS 的最后一个匹配字符时，在跳跃限制下的最长公共子序列长度。

注意：这里“以 s1[i] 和 s2[j] 结尾”意味着 s1[i] = s2[j]，且我们选择它们匹配。

状态转移时，我们需要从前面的某个匹配对 (i', j') 转移过来，满足：

  1. i' < i, j' < j
  2. s1[i'] = s2[j']（因为它是上一个匹配的字符）
  3. i - i' - 1 ≤ k 且 j - j' - 1 ≤ k

转移方程：

\[dp[i][j] = \max\{1, \max_{\substack{i' < i,\ j' < j \\ s1[i']=s2[j'] \\ i-i'-1\le k,\ j-j'-1\le k}} (dp[i'][j'] + 1) \} \]

其中，如果找不到这样的 (i', j')，那么 dp[i][j] = 1（只匹配当前字符）。

最终答案是所有 dp[i][j] 的最大值。

第三步：直接实现的复杂度问题

如果直接按照上述状态转移，我们需要枚举所有 (i', j')，总复杂度是 O(n²m²)，这太高。
我们需要优化。

第四步：优化思路

观察条件：

  1. i - i' - 1 ≤ k → i' ≥ i - k - 1
  2. j - j' - 1 ≤ k → j' ≥ j - k - 1

所以 i' 的取值范围是 [i-k-1, i-1] 且 i' ≥ 0。
同理 j' 的范围是 [j-k-1, j-1] 且 j' ≥ 0。

那么我们要在这样一个矩形区域内（最多 (k+1)×(k+1) 大小）找到所有 s1[i'] = s2[j'] 的位置，并取 dp[i'][j'] 的最大值再加 1。

因为字符集有限（假设是小写字母 26 个），我们可以这样优化：

  • 对于每个字符 ch，维护在 s2 中最近出现该字符的位置的表，但这里更直接的方法：
  • 我们枚举 i' 从 max(0, i-k-1) 到 i-1，对于每个 i'，字符 s1[i'] 是固定的，我们只需要在 j' 的范围 [max(0, j-k-1), j-1] 内，找到那些 s2[j'] = s1[i'] 的位置，取它们的 dp[i'][j'] 最大值。

所以可以：
预先用数组 best[i'][c] 表示在 s2 中，对于字符 c，在位置 j' 的某个范围内的最大 dp[i'][j'] 值。

但这里更简单：
我们可以在递推时，在第二层循环中，记录在当前的 i 下，对于每个字符 c，在 j' 的有效范围内，dp[i'][j'] 的最大值。

但要注意，i' 也是变动的，我们每次计算 dp[i][j] 时，i' 的范围是固定的，我们可以用另一个辅助数组 maxDp[ch][j'] 来记录对于字符 ch，在 s2 的位置 j' 时的最大 dp 值，但需要保证 i' 也在有效范围。

更直观的优化：
因为 k 一般不大，我们可以直接枚举 i' 和 j' 在 k+1 的窗口内，这样复杂度是 O(nm k²)，如果 k 很小，可以接受。

第五步：简化的动态规划定义

另一种更简单的状态设计：
定义 dp[i][j] 表示考虑 s1[0..i] 和 s2[0..j] 的满足跳跃限制的 LCS 长度，并且不一定以 s1[i] 和 s2[j] 结尾。
但这样很难控制跳跃限制。

为了更容易处理，我们定义：
dp[i][j] 表示以 s1[i] 和 s2[j] 结尾的满足跳跃限制的 LCS 长度，且 s1[i] = s2[j]。

那么初始化：如果 s1[i] = s2[j]，则至少为 1。

然后我们向前找 (i', j') 满足：

  • i' ∈ [max(0, i-k-1), i-1]
  • j' ∈ [max(0, j-k-1), j-1]
  • s1[i'] = s2[j']
  • 用 dp[i'][j'] 更新。

由于窗口大小为 O(k)×O(k)，可以直接枚举。
复杂度 O(nm k²)。

第六步：算法步骤

  1. 初始化 dp[n][m] 为 0。
  2. 遍历 i = 0..n-1, j = 0..m-1：
    • 如果 s1[i] != s2[j]，dp[i][j] = 0（因为不以它们结尾）。
    • 如果 s1[i] = s2[j]，则 dp[i][j] = 1（至少自身一个字符作为序列）。
      然后枚举 i' 从 max(0, i-k-1) 到 i-1，枚举 j' 从 max(0, j-k-1) 到 j-1：
      如果 s1[i'] = s2[j']，则 dp[i][j] = max(dp[i][j], dp[i'][j'] + 1)。
  3. 最终答案是 max(dp[i][j])，如果全为 0，则答案为 0。

第七步：例子验证

例：

s1 = "abcde", s2 = "ace", k = 1
n=5, m=3

初始化 dp 全 0。

i=0(a), j=0(a) 相等，dp=1。
i=0(a), j=1(c) 不等，dp=0。
i=0(a), j=2(e) 不等，dp=0。

i=1(b), j=0(a) 不等。
i=1(b), j=1(c) 不等。
i=1(b), j=2(e) 不等。

i=2(c), j=0(a) 不等。
i=2(c), j=1(c) 相等，dp=1，向前找：
i'∈[max(0,2-1-1)=0, 1]，即 {0,1}
j'∈[max(0,1-1-1)=0, 0]，即 {0}
检查 (i',j')=(0,0)：s1[0]=a, s2[0]=a 相等，且 dp[0][0]=1，则 dp[2][1]=max(1,1+1)=2。

i=3(d), j=0(a) 不等。
i=3(d), j=1(c) 不等。
i=3(d), j=2(e) 不等。

i=4(e), j=0(a) 不等。
i=4(e), j=1(c) 不等。
i=4(e), j=2(e) 相等，dp=1，向前找：
i'∈[max(0,4-1-1)=2, 3]，即 {2,3}
j'∈[max(0,2-1-1)=0, 1]，即 {0,1}
检查 (2,0): s1[2]=c, s2[0]=a 不等。
(2,1): s1[2]=c, s2[1]=c 相等，dp[2][1]=2，则 dp[4][2]=max(1,2+1)=3。

最终 max dp=3，正确。

第八步：复杂度与小结

  • 时间复杂度：O(nm k²)，当 k 较小或为常数时接近 O(nm)。
  • 空间复杂度：O(nm)，可优化到 O(m k) 但较复杂。

这个题目是 LCS 的变种，增加了跳跃次数的限制，通过限制前驱匹配的范围来实现，是线性动态规划中带窗口优化的一个典型例子。

如果你理解了，我可以再给你一个相关变种题目，比如“跳跃限制”改为“总跳过字符数有限制”而不是“每段跳过字符数有限制”，这样状态设计会更不同。你想继续探讨吗？

线性动态规划：最长公共子序列的变种——带字符跳跃限制的最长公共子序列 题目描述 给定两个字符串 s1 和 s2 ，以及一个整数 k 。 要求找到它们的最长公共子序列（LCS），但有一个额外限制： 在匹配过程中， 每次跳过（不匹配）的连续字符数不能超过 k 个 。 注意 ： 我们定义“跳过”为：在匹配某一个字符串的字符时，可以跳过该字符串中的若干字符，直接匹配后面的字符。 但跳过的连续字符数量不能超过 k ，否则这个匹配序列无效。 需要返回这个限制下最长公共子序列的长度。 示例 ： 正常 LCS 是 "ace"，长度 3。 这里限制 k=1，意味着在匹配过程中，如果在某个字符串中跳过字符，连续跳过不能超过 1 个。 对于这个例子，正常匹配 "a"、"c"、"e" 时，在 s1 中匹配 "a" 后，下一个匹配 "c" 需要跳过 s1 中的 'b'，只跳过 1 个字符，满足条件；匹配 "e" 时，跳过 s1 中的 'd'，也只跳过 1 个字符，满足条件，所以答案 = 3。 另一个例子 ： k=0 表示不允许跳过任何字符，也就是必须按顺序完全匹配 s2 在 s1 中连续出现，但这里 s2 在 s1 中不是连续的（a...c...f...g），所以无法匹配长度为 4 的序列，因为从 a 到 c 必须跳过 b，跳过了 1 个字符，违反 k=0 规则。 但我们可以匹配 "a"、"c"、"f"、"g" 吗？从 a 到 c 跳过 b（跳过 1 个字符，不允许，k=0 要求跳过数为 0），所以只有连续子串才合法。 仔细分析：k=0 时，这个“LCS 带跳跃限制”退化为寻找最长的公共子串（连续公共子序列），但注意这里是 在两个字符串中都必须连续 吗？不是，规则是“跳过连续字符数不超过 k”，k=0 时在两个字符串中都不能跳过任何字符，所以必须是两个字符串的公共子串（在两个字符串中都连续出现）。 我们这里先明确：跳过的定义是 在单个字符串中 匹配下一个字符时，跳过的该字符串的连续字符数。 逐步分析 第一步：理解“跳过”的定义 假设我们已匹配了 LCS 的某一部分，最后一个匹配的字符是 s1[i] 与 s2[j] ，接下来要匹配下一个字符，需要在 s1 中找到下一个匹配位置 i' > i ，在 s2 中找到 j' > j ，使得 s1[i'] = s2[j'] 。 在 s1 中，从 i+1 到 i'-1 这些字符是被跳过的，跳过的数量是 (i' - i - 1) 。 在 s2 中，从 j+1 到 j'-1 这些字符是被跳过的，跳过的数量是 (j' - j - 1) 。 题目限制：在 每个字符串中 ，每次匹配时跳过的连续字符数不能超过 k。 也就是说： \[ i' - i - 1 \le k \quad \text{且} \quad j' - j - 1 \le k \] 并且 这两个条件必须同时满足 ，否则这次匹配就是无效的。 第二步：动态规划状态设计 设 dp[i][j] 表示以 s1[i] 和 s2[j] 作为 LCS 的 最后一个匹配字符 时，在跳跃限制下的最长公共子序列长度。 注意：这里“以 s1[ i] 和 s2[ j] 结尾”意味着 s1[i] = s2[j] ，且我们选择它们匹配。 状态转移时，我们需要从前面的某个匹配对 (i', j') 转移过来，满足： i' < i , j' < j s1[i'] = s2[j'] （因为它是上一个匹配的字符） i - i' - 1 ≤ k 且 j - j' - 1 ≤ k 转移方程： \[ dp[ i][ j] = \max\{1, \max_ {\substack{i' < i,\ j' < j \\ s1[ i']=s2[ j'] \\ i-i'-1\le k,\ j-j'-1\le k}} (dp[ i'][ j' ] + 1) \} \] 其中，如果找不到这样的 (i', j') ，那么 dp[i][j] = 1 （只匹配当前字符）。 最终答案是所有 dp[i][j] 的最大值。 第三步：直接实现的复杂度问题 如果直接按照上述状态转移，我们需要枚举所有 (i', j') ，总复杂度是 O(n²m²)，这太高。 我们需要优化。 第四步：优化思路 观察条件： i - i' - 1 ≤ k → i' ≥ i - k - 1 j - j' - 1 ≤ k → j' ≥ j - k - 1 所以 i' 的取值范围是 [i-k-1, i-1] 且 i' ≥ 0 。 同理 j' 的范围是 [j-k-1, j-1] 且 j' ≥ 0 。 那么我们要在这样一个矩形区域内（最多 (k+1)×(k+1) 大小）找到所有 s1[i'] = s2[j'] 的位置，并取 dp[i'][j'] 的最大值再加 1。 因为字符集有限（假设是小写字母 26 个），我们可以这样优化： 对于每个字符 ch ，维护在 s2 中最近出现该字符的位置的表，但这里更直接的方法： 我们枚举 i' 从 max(0, i-k-1) 到 i-1 ，对于每个 i' ，字符 s1[i'] 是固定的，我们只需要在 j' 的范围 [max(0, j-k-1), j-1] 内，找到那些 s2[j'] = s1[i'] 的位置，取它们的 dp[i'][j'] 最大值。 所以可以： 预先用数组 best[i'][c] 表示在 s2 中，对于字符 c，在位置 j' 的某个范围内的最大 dp[i'][j'] 值。 但这里更简单： 我们可以在递推时，在第二层循环中，记录在当前的 i 下，对于每个字符 c ，在 j' 的有效范围内， dp[i'][j'] 的最大值。 但要注意， i' 也是变动的，我们每次计算 dp[i][j] 时， i' 的范围是固定的，我们可以用另一个辅助数组 maxDp[ch][j'] 来记录对于字符 ch ，在 s2 的位置 j' 时的最大 dp 值，但需要保证 i' 也在有效范围。 更直观的优化： 因为 k 一般不大，我们可以直接枚举 i' 和 j' 在 k+1 的窗口内，这样复杂度是 O(nm k²)，如果 k 很小，可以接受。 第五步：简化的动态规划定义 另一种更简单的状态设计： 定义 dp[i][j] 表示考虑 s1[0..i] 和 s2[0..j] 的满足跳跃限制的 LCS 长度，并且 不一定以 s1[ i] 和 s2[ j] 结尾 。 但这样很难控制跳跃限制。 为了更容易处理，我们定义： dp[i][j] 表示以 s1[i] 和 s2[j] 结尾的满足跳跃限制的 LCS 长度，且 s1[i] = s2[j] 。 那么初始化：如果 s1[i] = s2[j] ，则至少为 1。 然后我们向前找 (i', j') 满足： i' ∈ [max(0, i-k-1), i-1] j' ∈ [max(0, j-k-1), j-1] s1[i'] = s2[j'] 用 dp[i'][j'] 更新。 由于窗口大小为 O(k)×O(k)，可以直接枚举。 复杂度 O(nm k²)。 第六步：算法步骤 初始化 dp[n][m] 为 0。 遍历 i = 0..n-1 , j = 0..m-1 ： 如果 s1[i] != s2[j] ， dp[i][j] = 0 （因为不以它们结尾）。 如果 s1[i] = s2[j] ，则 dp[i][j] = 1 （至少自身一个字符作为序列）。 然后枚举 i' 从 max(0, i-k-1) 到 i-1 ，枚举 j' 从 max(0, j-k-1) 到 j-1 ： 如果 s1[i'] = s2[j'] ，则 dp[i][j] = max(dp[i][j], dp[i'][j'] + 1) 。 最终答案是 max(dp[i][j]) ，如果全为 0，则答案为 0。 第七步：例子验证 例： 初始化 dp 全 0。 i=0(a), j=0(a) 相等，dp=1。 i=0(a), j=1(c) 不等，dp=0。 i=0(a), j=2(e) 不等，dp=0。 i=1(b), j=0(a) 不等。 i=1(b), j=1(c) 不等。 i=1(b), j=2(e) 不等。 i=2(c), j=0(a) 不等。 i=2(c), j=1(c) 相等，dp=1，向前找： i'∈[ max(0,2-1-1)=0, 1 ]，即 {0,1} j'∈[ max(0,1-1-1)=0, 0 ]，即 {0} 检查 (i',j')=(0,0)：s1[ 0]=a, s2[ 0]=a 相等，且 dp[ 0][ 0]=1，则 dp[ 2][ 1 ]=max(1,1+1)=2。 i=3(d), j=0(a) 不等。 i=3(d), j=1(c) 不等。 i=3(d), j=2(e) 不等。 i=4(e), j=0(a) 不等。 i=4(e), j=1(c) 不等。 i=4(e), j=2(e) 相等，dp=1，向前找： i'∈[ max(0,4-1-1)=2, 3 ]，即 {2,3} j'∈[ max(0,2-1-1)=0, 1 ]，即 {0,1} 检查 (2,0): s1[ 2]=c, s2[ 0 ]=a 不等。 (2,1): s1[ 2]=c, s2[ 1]=c 相等，dp[ 2][ 1]=2，则 dp[ 4][ 2 ]=max(1,2+1)=3。 最终 max dp=3，正确。 第八步：复杂度与小结 时间复杂度：O(nm k²)，当 k 较小或为常数时接近 O(nm)。 空间复杂度：O(nm)，可优化到 O(m k) 但较复杂。 这个题目是 LCS 的变种，增加了跳跃次数的限制，通过限制前驱匹配的范围来实现，是线性动态规划中带窗口优化的一个典型例子。 如果你理解了，我可以再给你一个相关变种题目，比如“跳跃限制”改为“总跳过字符数有限制”而不是“每段跳过字符数有限制”，这样状态设计会更不同。你想继续探讨吗？