最长公共子序列的变种：带字符跳跃限制的最长公共子序列
题目描述
给定两个字符串 s 和 t，以及一个整数 k。我们需要找到它们的最长公共子序列（LCS），但有一个特殊限制：在原字符串 s 中，所选取的用于构成 LCS 的字符之间的索引差不能超过 k。换句话说，假设在 s 中选取的子序列对应的索引是 i1 < i2 < ... < im，在 t 中对应的索引是 j1 < j2 < ... < jm，则对于任意相邻的索引对 (i_{p}, i_{p+1})，需要满足 i_{p+1} - i_{p} ≤ k。
目标
在满足上述跳跃限制的条件下，求最长公共子序列的长度。
示例
例如：
s = "abcde"，t = "ace"，k = 2。
普通 LCS 是 "ace"，长度 3。
但这里在 s 中，"a"（索引 0）、"c"（索引 2）、"e"（索引 4）之间的相邻索引差：
i2 - i1 = 2 - 0 = 2（满足 ≤ 2）i3 - i2 = 4 - 2 = 2（满足 ≤ 2）
所以结果就是 3。
如果k = 1，则"ace"不合法（因为索引差 2 > 1），最长可能 LCS 是"ac"或"ce"长度 2。
解题思路
第一步：定义状态
这是一个线性动态规划问题，但有两个字符串，并且增加了索引差限制。
我们定义状态：
dp[i][j] 表示以 s[i] 和 t[j] 作为公共子序列的最后一个字符时，在 s 中相邻索引差 ≤ k 限制下的最大长度。
注意：我们要求“以 s[i] 和 t[j] 结尾”意味着这个公共字符必须是子序列的最后一个匹配。
状态转移时，我们需要往前找 s 中在 i 之前的某个位置 i'，且 i - i' ≤ k，同时 t 中在 j 之前的某个位置 j'，且 s[i'] = t[j']，然后接上当前字符。
第二步：状态转移方程
如果 s[i] == t[j]，那么：
dp[i][j] = 1 + max{ dp[i'][j'] }
其中 max 取所有满足以下条件的 (i', j')：
0 ≤ i' < i，0 ≤ j' < ji - i' ≤ ks[i'] == t[j']
如果 s[i] != t[j]，则 dp[i][j] 可以认为不构成以它们结尾的公共子序列，但为了计算方便，我们让 dp[i][j] = 0 表示不以这对字符结尾。
边界条件：如果前面没有匹配的，dp[i][j] 至少可以是 1（只用当前匹配的字符本身）。
第三步：优化转移
直接按上述转移会达到 O(n²m²) 的复杂度（n,m 为字符串长度），不可接受。
我们需要优化这个“往前找”的过程。
注意 i - i' ≤ k 是一个“有限窗口”限制，也就是说，当固定 i,j 时，我们只需要考虑 i' 在 [i-k, i-1] 范围内，且 j' 在 [0, j-1] 范围内，并满足 s[i'] == t[j'] 的最大 dp[i'][j']。
我们可以用一个辅助数组来加速查询：
定义 pre_max[j'] 表示在上一轮 i' 循环中，对于某个固定的 i'，在所有 j' 中 dp[i'][j'] 的值。
但更直接的方法：
我们反过来遍历，当固定 i 时，i' 取值范围很小（最多 k 个），所以对每个 i' 我们可以维护一个数组，记录 dp[i'][j'] 的前缀最大值。
但更简单的实现是：
用三维状态 f[i][j][p] 表示以 s[i] 和 t[j] 结尾，且这个字符是子序列的第 p 个字符……这样反而复杂。
更好的方法：
定义 f[i][j] 表示考虑 s[0..i] 和 t[0..j]，并且公共子序列的最后一个字符匹配是 s[i] 和 t[j] 时的最大长度。
我们依然需要往前找 (i', j') 且 i-i' ≤ k。
我们可以反过来固定 i'，然后更新所有 i = i'+d（d ≤ k） 的状态。
不过更简单的是用两层循环，在 i 循环时，对每个 j 往前找时，只需在 i 之前的 k 个位置找，并且同时满足 s[i']==t[j'] 的 j' 在 t 中位置小于 j。
这其实等价于：
对每个 i，对每个 j，如果 s[i]==t[j]，则
dp[i][j] = 1 + max{ dp[i'][j'] } 对 i' 在 [max(0,i-k), i-1]，j' 在 [0, j-1] 且 s[i']==t[j']。
这个 max 可以用另一个数组 max_dp[i'][j'] 在 j' 维度的前缀最大值来快速得到。
具体来说，我们预先计算 prefix_max[i'][v] 表示对于固定的 i'，在 t 的前 v 个字符中，满足 s[i']==t[q] 的 dp[i'][q] 的最大值。
但 s[i'] 是固定的字符，我们可以用字符索引来快速查找。
第四步：最终的状态设计与转移
我们采用二维状态 dp[i][j] 表示以 s[i] 和 t[j] 结尾的满足跳跃限制的最长公共子序列长度。
转移：
如果 s[i] != t[j]，dp[i][j] = 0（因为我们定义它是以这对字符结尾的情况，如果不相等自然不能结尾）。
如果 s[i] == t[j]：
dp[i][j] = 1（至少长度 1）
然后我们查看 i' 在 [max(0, i-k), i-1] 范围内，且 s[i'] == 某个字符，这个字符在 t 中出现位置 j' < j 的所有可能。
为了快速得到这个最大值，我们维护一个数组 best[i'][c] 表示在 s 的位置 i'，字符 c 在 t 中所有位置 j' 对应的 dp[i'][j'] 的最大值。
但我们也可以更直接：
用 prev[i'][j'] 表示 dp[i'][j'] 的值，然后在 i 循环中，维护一个数组 max_len[i'][j'] 表示对于 i' 来说，t[0..j'] 中 dp[i'][*] 的最大值。
但注意必须匹配 s[i'] == t[j'] 才有效，所以我们可以用 max_val[i'][ch] 表示 i' 位置，字符 ch 在 t 中位置 j' 的 dp 最大值。
实现步骤：
-
初始化 dp 为 0。
-
遍历 i 从 0 到 n-1：
遍历 j 从 0 到 m-1：
如果 s[i] == t[j]：
初始化 dp[i][j] = 1
对 p 从 max(0, i-k) 到 i-1：
字符 ch = s[p]
我们要在 t[0..j-1] 中找到所有 ch 的位置，取 dp[p][q] 的最大值。
为了 O(1) 时间得到这个值，我们预先记录在位置 p 时，字符 ch 对应的最大 dp 值（考虑 t 的前 j-1 个位置）。
但这里 j 是当前循环变量，所以我们需要在 j 循环中逐步更新这个“历史最大值”。
因此我们可以用max_dp[p][ch]表示在 s 位置 p，字符 ch 在 t 的前 j-1 个位置中出现的 dp 最大值。
在计算 dp[i][j] 时，查询max_dp[p][s[i']]即可。 -
更新
max_dp[i][s[i]]在 j 循环中，当计算完 dp[i][j] 后，更新：
max_dp[i][s[i]] = max(max_dp[i][s[i]], dp[i][j])。
这样，当未来的 i2 访问 i 时，就能得到正确的历史最大值。
第五步：算法步骤整理
- 初始化
dp[n][m]=0，max_dp[n][26]=0（26 是字符集大小）。 - 遍历 i = 0 to n-1：
遍历 j = 0 to m-1：
如果 s[i] == t[j]：
令 val = 1
对 p 从 max(0, i-k) 到 i-1：
val = max(val, 1 + max_dp[p][s[i] 的字符索引])
令 dp[i][j] = val
更新 ans = max(ans, val)
否则 dp[i][j] = 0
更新 max_dp[i][t[j] 的字符索引] = max(max_dp[i][t[j] 的字符索引], dp[i][j])
第六步：复杂度
时间复杂度 O(n * m * k)，因为对每个 (i,j) 对，需要检查前 k 个 i'。
空间复杂度 O(n * 26 + n * m)，但 m 很大时内存大，可优化到 O(n * 26) 如果我们不存整个 dp 矩阵，只存上一行和 max_dp 数组。
第七步：最终答案
答案就是所有 dp[i][j] 的最大值。
示例推演（k=2）
s = "abcde"
t = "ace"
n=5, m=3
初始化 max_dp 全 0。
i=0, s[0]='a'
j=0, t[0]='a' 相等
p 从 max(0,0-2)=0 到 -1 无，val=1
dp[0][0]=1
max_dp[0]['a']=1
j=1, t[1]='c' 不相等，dp[0][1]=0，max_dp[0]['c']=max(0,0)=0
j=2, t[2]='e' 不相等，dp[0][2]=0，max_dp[0]['e']=0
i=1, s[1]='b'
j=0, 'b'!='a'，dp=0，max_dp[1]['a']=0
j=1, 'b'!='c'，dp=0，max_dp[1]['c']=0
j=2, 'b'!='e'，dp=0，max_dp[1]['e']=0
i=2, s[2]='c'
j=0, 'c'!='a'，dp=0，max_dp[2]['a']=0
j=1, 'c'=='c' 相等
检查 p 从 max(0,2-2)=0 到 1：
p=0, s[0]='a'，max_dp[0]['c']=0 → 1+0=1
p=1, s[1]='b'，max_dp[1]['c']=0 → 1+0=1
val=1，dp[2][1]=1
max_dp[2]['c']=1
j=2, 'c'!='e'，dp=0，max_dp[2]['e']=0
i=3, s[3]='d'（在 t 中没有 'd'，所有 dp=0，略过）
i=4, s[4]='e'
j=2, 'e'=='e' 相等
p 从 max(0,4-2)=2 到 3：
p=2, s[2]='c'，max_dp[2]['e']=0 → 1+0=1
p=3, s[3]='d'，max_dp[3]['e']=0 → 1+0=1
但注意 p=0 不在窗口内（i-p=4>2 不可）。
val=1 但还有 p=1? i-p=3>2 不可，所以只有 p=2,3。
检查 p=1? i-p=3>2 不可。
检查 p=0? i-p=4>2 不可。
但等等，我们还需要检查 p=2,3 之前是否有匹配的 e 的前驱。
但 e 的前一个字符是 c，c 在 s[2]，匹配 t[1] 时 dp[2][1]=1。
我们算法中，在 i=4,j=2 时，p=2 时，max_dp[2]['e'] 是 0，因为 e 在 t 中 j=2 才出现，而 max_dp[2]['e'] 只在 t[j]=e 时更新，但 e 在 t 中只有 j=2，所以 max_dp[2]['e'] 是 dp[2][2]? 不，dp[2][2] 是 0，因为 s[2]!='e'。
但我们需要的是字符 'c' 的前驱，不是 'e'。
实际上，我们的设计有缺陷：max_dp[p][ch] 存储的是 s[p] 与 t 中字符 ch 匹配的最大 dp 值。
在 i=4 时，s[4]='e'，我们需要找 p 使得 s[p]==t[j'] 其中 t[j'] 是 'e' 的前一个匹配字符（即 'c'），也就是 s[p]=='c'，且 j'<2。
所以应该用 max_dp[p][t[j-1]] 吗？不，因为 LCS 的前一个字符是任意的，不一定是 t[j-1]。
所以我们的“字符跳跃限制”只限制 s 中的索引差，不限制 t 中的间隔，所以 t 中前一个匹配字符可以是任何位置 <j 的。
因此，在 p 循环中，我们需要的是 max_dp[p][*] 的最大值，不限于某个字符。
但必须满足 s[p]==t[q] 才有 dp[p][q] 值。
所以我们用 max_dp[p] 表示在位置 p，所有字符的最大 dp 值。
但这样，我们无法知道 t 中对应位置是否 <j，因为 max_dp[p] 可能来自 t 中位置 ≥j 的情况，这会导致非法转移。
为了避免这个问题，我们必须在 j 循环时，按顺序更新，使得在计算 dp[i][j] 时，max_dp[p] 只包含 t 中位置 <j 的信息。
我们可以通过遍历 j 时，在计算完 dp[i][j] 后更新 max_dp[i][s[i]]，但这是对当前 i 的更新。
对于 p<i 的 max_dp[p]，它已经在之前的 j 循环中更新了，所以当我们计算 dp[i][j] 时，max_dp[p] 可能已经包含 t 中 j 之后的信息。
因此必须区分 j 的顺序，所以应该用二维数组 max_dp[p][j] 表示考虑 t[0..j] 的最大值。
但这样空间 O(nm) 又大了。
我们可以优化为：在 j 循环中，维护一个临时数组 tmp_max[p] 表示在当前的 j 下，max_dp[p] 的值。
但这样每次 j 循环要更新 k 个 p 的 tmp_max，复杂度 O(mn*k) 可接受。
修正后的简化算法（O(nmk) 直接法）
为了清晰，我们放弃优化，直接用 O(nmk) 的显式循环：
- 初始化 dp[n][m]=0。
- 遍历 i = 0 to n-1：
遍历 j = 0 to m-1：
如果 s[i] == t[j]：
令 dp[i][j] = 1
对 p 从 max(0, i-k) 到 i-1：
对 q 从 0 到 j-1：
如果 s[p] == t[q]：
dp[i][j] = max(dp[i][j], dp[p][q] + 1) - 答案 = max(dp[i][j])
这样逻辑简单，但复杂度高。
对于小 k 可用。
如果你希望看到优化到 O(nmK) 的最终版本（K 是字符集大小），我可以再进一步推导，但核心思路是上面这样。
总结：
这道题是 LCS 的变种，增加了在 s 中相邻匹配字符的索引距离限制。
我们用动态规划，状态表示以 s[i] 和 t[j] 结尾的合法 LCS 长度，转移时检查 s 中前 k 个位置，在 t 中前 j-1 个位置中的最大 dp 值。
利用前缀最大数组可以优化到 O(nm|Σ|) 或 O(nmmin(k, |Σ|)) 的复杂度。