线性动态规划：最长公共子序列的变种——带字符必须按顺序出现限制的最长公共子序列（进阶版：限制某些字符必须连续出现k次，且总出现次数有限制） 题目描述 给定两个字符串 s 和 t ，以及一个字符集合 C （例如 C = {'a', 'b'} ）。要求找到 s 和 t 的最长公共子序列（LCS），但需满足以下限制： 顺序限制 ：子序列中所有属于 C 的字符必须按照它们在 s 中首次出现的顺序出现（即保留相对顺序）。 连续出现限制 ：子序列中每个属于 C 的字符必须连续出现至少 k 次（例如 k=2 ，则 'a' 必须连续出现至少2次）。 总出现次数限制 ：每个属于 C 的字符在子序列中的总出现次数不能超过一个上限 max_count （例如 max_count=3 ）。 示例 设 s = "aabcbd" , t = "acbbad" , C = {'a', 'b'} , k = 2 , max_count = 3 。 有效子序列示例： "aab" （ 'a' 连续2次，总次数2； 'b' 总次数1）。 无效子序列示例： "ab" （ 'a' 未连续出现至少2次）。 解题过程 此问题在标准LCS动态规划基础上，需增加状态维度来跟踪限制条件。我们逐步构建解法。 步骤1：定义状态 设 dp[i][j][x][y] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，当前正在积累的字符 ch （属于 C ）已连续出现 x 次，且该字符总出现次数为 y 时的最长公共子序列长度。 i ： s 的索引（0 ≤ i ≤ len(s)） j ： t 的索引（0 ≤ j ≤ len(t)） ch ：当前积累的字符（属于 C ），需枚举所有可能。 x ：当前字符 ch 的连续出现次数（1 ≤ x ≤ k） y ：当前字符 ch 的总出现次数（1 ≤ y ≤ max_ count） 步骤2：状态转移 分为两种情况： 不匹配当前字符 ： 跳过 s[i] ： dp[i][j][x][y] = dp[i-1][j][x][y] 跳过 t[j] ： dp[i][j][x][y] = dp[i][j-1][x][y] 取最大值。 匹配字符 （当 s[i] = t[j] 时）： 若 s[i] 不属于 C ：直接加入子序列， dp[i][j][x][y] = dp[i-1][j-1][x][y] + 1 。 若 s[i] 属于 C ： 若当前积累字符就是 s[i] ： 若 x < k ：继续积累， dp[i][j][x+1][y+1] = max(自身, dp[i-1][j-1][x][y] + 1) 若 x = k ：可继续积累或重置（因为已满足连续k次），但总次数不能超限： 继续积累： dp[i][j][k][y+1] = ... （需 y+1 ≤ max_count ） 重置积累： dp[i][j][1][y+1] = ... （开始新一段积累） 若当前积累字符不是 s[i] ： 必须重置积累，且只有在前一段积累已满足连续k次时才能切换： dp[i][j][1][1] = max(自身, dp[i-1][j-1][k][y_prev] + 1) （其中 y_prev 是前字符的总次数）。 步骤3：初始化 dp[0][j][x][y] = 0 对任意 j, x, y dp[i][0][x][y] = 0 对任意 i, x, y 初始积累状态： dp[0][0][0][0] = 0 ，表示空子序列。 步骤4：最终答案 遍历所有可能的 ch （属于 C ）、 x （1 ≤ x ≤ k）、 y （1 ≤ y ≤ max_ count），取 dp[len(s)][len(t)][x][y] 的最大值。同时需确保当前积累字符的连续次数 x 满足 x ≥ k （除非未积累任何 C 字符）。 简化与优化 实际编码时，可将 ch 作为外层循环，避免状态维度过高。 利用滚动数组优化空间复杂度。 预处理 s 和 t 中 C 字符的位置，加速匹配。 此解法通过扩展状态维度，将复杂限制融入动态规划框架，确保在O(n²·k·max_ count·|C|)时间内求解。