最长公共子序列的变种：带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现） 题目描述： 给定两个字符串s和t，以及一个字符集合C和一个整数k。要求找到s和t的最长公共子序列，且满足：对于集合C中的每个字符，如果在子序列中出现，则必须连续出现至少k次。如果无法连续出现k次，则该字符不能出现在子序列中。 解题过程： 问题分析： 这是LCS问题的变种，增加了字符出现次数的限制条件 关键难点：需要跟踪每个字符的连续出现次数 需要记录状态：当前匹配位置、字符连续出现情况 状态定义： 定义dp[ i][ j][ c][ cnt ]表示： 考虑s的前i个字符和t的前j个字符 当前正在匹配字符c（c=0表示没有正在匹配的字符） 当前字符c已经连续出现了cnt次 值为这种情况下能得到的最长公共子序列长度 状态转移： 情况1：不匹配当前字符 dp[ i][ j][ c][ cnt] = max(dp[ i-1][ j][ c][ cnt], dp[ i][ j-1][ c][ cnt ]) 情况2：s[ i] = t[ j ]，且等于当前匹配字符c 如果c ≠ 0且s[ i ] = c： dp[ i][ j][ c][ cnt] = max(dp[ i][ j][ c][ cnt], dp[ i-1][ j-1][ c][ cnt-1 ] + 1) 情况3：s[ i] = t[ j ]，但不等于当前匹配字符c 子情况3.1：开始匹配新字符（c ∈ C） 如果cnt ≥ k 或者 c = 0（之前没有匹配字符）： dp[ i][ j][ s[ i]][ 1] = max(dp[ i][ j][ s[ i]][ 1], dp[ i-1][ j-1][ c][ cnt ] + 1) 子情况3.2：开始匹配新字符（c ∉ C） 可以直接开始匹配，无连续次数限制： dp[ i][ j][ s[ i]][ 1] = max(dp[ i][ j][ s[ i]][ 1], dp[ i-1][ j-1][ c][ cnt ] + 1) 边界条件： dp[ 0][ j][ c][ cnt ] = 0（s为空字符串） dp[ i][ 0][ c][ cnt ] = 0（t为空字符串） 初始状态：dp[ 0][ 0][ 0][ 0 ] = 0 结果计算： 结果 = max{ dp[ len(s)][ len(t)][ c][ cnt ] } 对所有c和cnt 注意：如果c ∈ C，必须满足cnt ≥ k 或 cnt = 0 优化考虑： 实际实现时，c可以用字符的ASCII码表示 cnt的最大值可以限制为k（超过k的部分没有额外意义） 使用滚动数组优化空间复杂度 这个算法通过四维DP表跟踪字符连续出现情况，确保满足题目中的限制条件，时间复杂度为O(n×m×|字符集|×k)。