线性动态规划：最长公共子序列的变种——带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现k次，且总出现次数有限制） 题目描述 给定两个字符串s和t，以及一个字符c的出现次数限制L（正整数）。要求找到s和t的一个最长公共子序列，使得字符c在子序列中出现的次数不超过L，并且字符c在子序列中必须连续出现至少k次（k为正整数，且k≤L）。也就是说，如果子序列中包含字符c，那么这些c必须连续出现（形成一个连续的c块），且这个连续块的长度至少为k，同时整个子序列中c的总出现次数不超过L。 解题过程 问题分析 这是最长公共子序列（LCS）问题的变种，增加了对特定字符c的出现限制 关键约束条件： 字符c必须连续出现（如果出现的话） 连续c块的长度≥k c的总出现次数≤L 需要设计特殊的状态表示来处理这些约束 状态定义 定义dp[ i][ j][ x][ y ]，其中： i: 在s中考虑前i个字符（0≤i≤len(s)） j: 在t中考虑前j个字符（0≤j≤len(t)） x: 当前已使用的c字符次数（0≤x≤L） y: 当前连续c块的状态： y=0: 当前没有活跃的c块 y=1: 当前有活跃的c块，且已连续y个c字符 状态转移方程 情况1 : s[ i-1] == t[ j-1 ] 如果当前字符不是c： dp[ i][ j][ x][ 0] = max(dp[ i][ j][ x][ 0], dp[ i-1][ j-1][ x][ 0 ] + 1) dp[ i][ j][ x][ 0] = max(dp[ i][ j][ x][ 0], dp[ i-1][ j-1][ x][ 1 ] + 1) // 结束c块 如果当前字符是c且x < L： // 开始新的c块（y从0到1） if y == 0: dp[ i][ j][ x+1][ 1] = max(dp[ i][ j][ x+1][ 1], dp[ i-1][ j-1][ x][ 0 ] + 1) // 继续当前c块 else: dp[ i][ j][ x+1][ y+1] = max(dp[ i][ j][ x+1][ y+1], dp[ i-1][ j-1][ x][ y ] + 1) 情况2 : s[ i-1] != t[ j-1 ] 跳过s的当前字符：dp[ i][ j][ x][ y] = max(dp[ i][ j][ x][ y], dp[ i-1][ j][ x][ y ]) 跳过t的当前字符：dp[ i][ j][ x][ y] = max(dp[ i][ j][ x][ y], dp[ i][ j-1][ x][ y ]) 边界条件 dp[ 0][ j][ 0][ 0 ] = 0（空s字符串） dp[ i][ 0][ 0][ 0 ] = 0（空t字符串） 其他状态初始化为负无穷（表示不可达） 最终答案 最终答案是所有满足以下条件的最大值： max(dp[ len(s)][ len(t)][ x][ y ])，其中： 如果y > 0（有活跃c块），则y必须≥k（满足连续k次要求） 如果y == 0（没有活跃c块），则直接满足条件 算法优化 由于状态空间为O(n²L²)，可能较大 可以通过滚动数组优化空间复杂度 对于y的维度，实际上只需要记录0,1,...,k,k+1（因为超过k的部分不影响结果） 示例演示 假设s="aabcc", t="aacbc", c='c', k=2, L=3 逐步计算： 匹配"aa"部分：正常LCS匹配 遇到第一个c时：可以开始c块，但需要连续至少2个c 继续匹配，确保c连续出现满足k=2的要求 最终找到满足条件的LCS 这个算法确保了在满足所有约束条件下找到最优解。