最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现k次） 题目描述 给定两个字符串 s1 和 s2 ，每个字符有一个权重（可能为负数）。要求找到 s1 和 s2 的一个公共子序列，满足以下条件： 子序列的权重和（即所有字符权重之和）非负。 子序列中某些指定字符（例如字符 'a' ）必须连续出现至少 k 次（若出现）。 目标是使子序列的权重和尽可能大。 示例 s1 = "aabc" , s2 = "aacb" ，字符权重： 'a' ：2， 'b' ：-1， 'c' ：3，要求 'a' 必须连续出现至少 k=2 次。 解：公共子序列 "aac" 的权重和为 2+2+3=7 （非负），但 'a' 未连续出现至少2次（中间有 'c' 隔开）；子序列 "aa" 权重和为 2+2=4 ，且 'a' 连续出现2次，满足条件。 解题步骤 1. 问题分析 本题结合了多种约束： 公共子序列（LCS）的基本结构。 字符权重和需非负。 特定字符必须连续出现至少 k 次。 需设计动态规划状态同时跟踪这些条件。 2. 状态设计 定义 dp[i][j][w][c][t] ： i ：考虑 s1 的前 i 个字符。 j ：考虑 s2 的前 j 个字符。 w ：当前子序列的权重和（可能为负，需离散化或偏移处理）。 c ：当前连续字符的计数（针对特定字符，如 'a' ）。 t ：标记是否已满足连续出现至少 k 次的条件（0/1）。 状态转移 ： 不选当前字符 ：继承 dp[i-1][j][w][c][t] 或 dp[i][j-1][w][c][t] 。 选当前字符 （仅当 s1[i-1] == s2[j-1] ）： 设字符为 ch ，权重为 weight 。 若 ch 不是特定字符（无需连续出现约束）： 重置连续计数 c=0 （因字符类型改变）。 新权重 w' = w + weight 。 继承之前的 t 。 若 ch 是特定字符（如 'a' ）： 连续计数 c' = c + 1 （若前一个字符也是 'a' ）或 c' = 1 （否则）。 更新 t' ：若 c' >= k ，则标记 t'=1 ，否则继承 t 。 更新 dp[i][j][w'][c'][t'] 。 3. 权重偏移处理 权重可能为负，需将权重范围平移至非负区间。设最小可能权重和为 min_w ，定义偏移量 offset = -min_w ，则实际状态中 w 存储 原始权重 + offset 。 4. 初始化和边界 dp[0][0][offset][0][0] = 0 （空序列权重为0，连续计数0，未满足条件）。 其他状态初始为负无穷（表示不可达）。 5. 结果提取 遍历所有 i 、 j 、 w （需满足 w - offset >= 0 ）、 c 、 t=1 （已满足连续条件），取最大权重和。 6. 优化 状态数可能较大，需根据实际权重范围离散化。若 k 较大，可限制连续计数 c 的最大值为 k （因超过 k 不影响条件判断）。 总结 本题通过扩展状态维度，同时跟踪权重和、连续计数和条件标记，将复杂约束融入动态规划框架。关键在于合理设计状态转移，处理权重偏移，并优化状态空间。