线性动态规划：最长公共子序列的变种——带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现） 题目描述 给定两个字符串 s1 和 s2 ，以及一个整数 k 和一个字符 c 。要求找出 s1 和 s2 的最长公共子序列（LCS），但该子序列必须满足：字符 c 在子序列中出现的次数 至少为 k 次 ，且所有 c 字符在子序列中必须 连续出现 （即不能间断）。例如： 输入： s1 = "aababc", s2 = "aacabb", c = 'a', k = 2 输出：4（解释：子序列 "aaba" 或 "aacb" 均满足条件，其中 'a' 连续出现至少2次） 解题过程 问题分析 基础问题是最长公共子序列（LCS），但增加了两个限制： 子序列中字符 c 的出现次数 ≥ k 。 所有 c 必须连续出现（即子序列中不能出现被非 c 字符隔开的 c ）。 关键点：连续出现的 c 可以视为一个整体段（称为" c -段"），子序列中至多包含一个 c -段。 状态定义 定义 dp[i][j][x][t] ： i ：考虑 s1 的前 i 个字符。 j ：考虑 s2 的前 j 个字符。 x ：当前已匹配的 c -段的长度（即连续 c 的个数）。若 x > 0 ，表示正在构建一个 c -段；若 x = 0 ，表示未开始或已结束 c -段。 t ：表示当前状态是否已满足 c 出现次数 ≥ k （ t = 1 表示已满足， t = 0 表示未满足）。 状态转移 情况1：不匹配当前字符 跳过 s1[i] 或 s2[j] ： dp[i][j][x][t] = max(dp[i-1][j][x][t], dp[i][j-1][x][t]) 情况2：匹配字符（s1[ i] == s2[ j]） 设当前字符为 ch ： 若 ch != c ： 如果 x = 0 （未在 c -段中），可以匹配该字符： dp[i][j][0][t] = max(dp[i][j][0][t], dp[i-1][j-1][0][t] + 1) 如果 x > 0 ，则不能匹配非 c 字符（因为会中断 c -段）。 若 ch == c ： 如果 x = 0 ，可以开始新的 c -段： dp[i][j][1][t'] = max(...) ，其中 t' = 1 if 1 >= k else t 。 如果 x > 0 ，可以扩展当前 c -段： dp[i][j][x+1][t'] = max(...) ，其中 t' = 1 if x+1 >= k else t 。 初始化 dp[0][j][0][0] = 0 ， dp[i][0][0][0] = 0 （空串时长度为0）。 其他状态初始为负无穷（表示不可达）。 最终答案 遍历所有 i , j ，取 dp[i][j][x][1] 的最大值（ x 任意，但需满足 t = 1 ）。 示例演示 （s1 = "aababc", s2 = "aacabb", c = 'a', k = 2） 匹配子序列 "aaba"：在 s1 中索引为 0,1,2,4，在 s2 中索引为 0,2,3,4，其中 'a' 连续出现2次（位置0-1），满足条件。 通过DP表逐步计算，最终得到最大长度为4。 关键点 通过 x 记录连续 c 的长度，确保连续性。 通过 t 标记是否已满足次数要求，避免无效状态。 时间复杂度 O(n²·k)，空间复杂度可优化至 O(n·k)。