最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现k次） 题目描述 给定两个字符串 s 和 t ，每个字符 c 有一个权重 w(c) （可能为负数）。要求找到 s 和 t 的一个公共子序列，使得： 子序列的权重和（即所有字符权重的总和）非负且尽可能大； 子序列中某些指定字符（例如字符 'a' ）必须连续出现至少 k 次（即如果 'a' 出现在子序列中，则所有 'a' 必须连续排列，且出现次数 ≥ k ，否则不能出现 'a' ）。 解题过程 本题是 LCS 的复杂变种，需同时处理权重约束和字符连续出现约束。我们使用动态规划，通过扩展状态定义来记录额外信息。 步骤 1：定义状态 设 dp[i][j][sum][cnt][ch] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，当前公共子序列的权重和为 sum ，且最后一个字符为 ch （ ch 为特定字符或空标记），该字符已连续出现 cnt 次的情况下，能否达到该状态（或记录最大权重）。但直接这样定义状态维度太高，需优化。 优化思路 ： 权重和非负约束 ：权重和只需记录非负部分，且可压缩为“当前权重和”与“历史最大权重和”的结合。实际处理时，我们关注最大权重和，可忽略中间负权值，但需确保最终和非负。 连续出现约束 ：仅对特定字符（如 'a' ）需连续出现 k 次。我们可在状态中记录当前连续字符及其次数，但仅当该字符为指定字符时才需要。 重新定义状态 ： 设 dp[i][j][lastChar][lastCount] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，当前公共子序列的最后一个字符是 lastChar （用整数表示，0 表示子序列为空），且该字符已连续出现 lastCount 次的情况下，能获得的最大权重和。若状态不可达，则设为负无穷。 步骤 2：状态转移 对于每个状态 (i, j, lastChar, lastCount) ，考虑下一步选择： 不匹配当前字符 ：跳过 s[i] 或 t[j] ，转移到 (i+1, j, lastChar, lastCount) 或 (i, j+1, lastChar, lastCount) 。 匹配字符 （当 s[i] == t[j] 时）：设当前字符为 c = s[i] ，权重为 w(c) 。 若 c == lastChar ：可扩展连续序列，新连续次数为 lastCount + 1 ，新权重为原权重加 w(c) 。转移到 (i+1, j+1, c, lastCount+1) 。 若 c != lastChar ：开始新连续段。但需检查旧字符的连续约束：若旧字符是指定字符且 lastCount < k ，则此转移非法（因为旧字符段未满足连续出现要求）。新状态为 (i+1, j+1, c, 1) ，权重加 w(c) 。 关键点 ：在结束一个字符段时（即当下一步匹配新字符或结束时），检查该段是否满足连续出现要求：若 lastChar 是指定字符且 lastCount < k ，则当前状态无效，不能用于转移。 步骤 3：初始化和边界 初始状态： dp[0][0][0][0] = 0 （空子序列，权重和为 0）。 边界： i 或 j 为 0 时，只有跳过字符的操作。 步骤 4：计算顺序 按 i 从 0 到 len(s) ， j 从 0 到 len(t) 遍历，内部循环遍历 lastChar 和 lastCount 。 步骤 5：答案提取 遍历所有 i , j ，以及所有 lastChar , lastCount ，检查是否满足连续约束（若 lastChar 是指定字符，则需 lastCount >= k 或 lastCount == 0 ），取权重和的最大值。 举例说明 设 s = "aab" , t = "acab" ，权重 w('a') = 1 , w('b') = -1 , w('c') = 2 ，指定字符 'a' 需连续出现 k=2 次。 有效子序列： "aa" （权重和 2，满足连续出现 2 次）， "a" 无效（连续出现 1 次 < 2）。 动态规划过程中，当匹配第二个 'a' 时，连续次数变为 2，状态变为有效。 总结 本题通过扩展 LCS 的状态定义，加入最后字符和连续次数的记录，从而处理权重和约束和字符连续出现约束。实际实现时需注意状态压缩（如权重和范围可能很大时可离散化或限制范围）。