最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现） 题目描述 给定两个字符串 s 和 t ，每个字符有一个权重（可能为负数）。要求找到 s 和 t 的一个公共子序列，满足： 权重和非负 ：子序列中所有字符的权重之和 ≥ 0。 连续字符限制 ：某些字符（例如 'a' ）在子序列中必须连续出现至少 k 次（若出现），否则不能包含该字符。 目标 ：在所有满足条件的公共子序列中，选取权重和最大的一个，并返回其权重和。若不存在满足条件的子序列，返回 0。 示例 s = "aabc" , t = "aacb" , 权重： a: 2 , b: -1 , c: 3 ，要求字符 'a' 必须连续出现至少 2 次。 可能公共子序列： "aa" （权重 4， 'a' 连续出现 2 次，合法）、 "aab" （权重 3，但 'a' 未连续出现 2 次？注意：这里 'a' 连续出现 2 次后接 'b' ，仍满足连续出现条件）、 "ac" （权重 5，但 'a' 只出现 1 次，违反连续出现限制，非法）。 最大权重和： "aa" （4）或 "aac" （7，需检查在 t 中是否连续？详细分析见下）。 解题过程 步骤 1：问题分析 此问题在经典 LCS 动态规划基础上，增加了三个约束： 字符权重 ：子序列权重和需 ≥ 0，且要最大化。 连续出现限制 ：某些字符若被选入子序列，则必须连续出现至少 k 次。 负权重允许 ：权重可能为负，需避免权重和变负。 难点在于连续出现限制会影响状态设计：不能仅记录当前匹配位置，还需记录当前已匹配的连续字符情况。 步骤 2：状态设计 定义 dp[i][j][w][c][len] ： i ：在 s 中匹配到第 i 个字符（1-based，0 表示未匹配）。 j ：在 t 中匹配到第 j 个字符。 w ：当前已选子序列的权重和（可能为负，但最终需 ≥ 0）。 c ：当前正在连续出现的字符（用字符索引表示，如 0 表示无连续字符）。 len ：当前字符 c 已连续出现的次数。 状态值表示是否存在这样的公共子序列（或存储最大权重，但 w 已作为状态维度）。 但五维状态可能过大，需优化： 将 w 范围限制为 [ 0, W_ max]（W_ max 为最大可能权重和），负权重状态可剪枝。 若字符集大小 C 固定，可接受。 简化：假设字符集较小（如 26 个字母）， k 固定。 步骤 3：状态转移 对于每个状态 (i, j, w, c, len) ，考虑下一步选择： 不匹配当前字符 ：转移到 (i+1, j, w, c, len) 或 (i, j+1, w, c, len) 。 匹配字符 x （若 s[i] == t[j] == x ）： 若 c == x ：可扩展连续字符，转移到 (i+1, j+1, w + weight[x], x, len+1) 。 若 c != x ：需检查上一段连续字符是否满足限制（若 c 属于受限集，则 len >= k 才合法）。然后新字符 x 开始连续段，转移到 (i+1, j+1, w + weight[x], x, 1) 。 注意 ：若 x 属于受限字符集，则新连续段长度必须最终 ≥ k 才合法，但可在后续匹配中扩展，因此状态中保留 len 。 步骤 4：初始化和答案提取 初始状态： (0, 0, 0, 0, 0) 表示未匹配任何字符。 最终答案：所有 (n, m, w, c, len) 中 w >= 0 且若 c 受限则 len >= k 的最大 w 。 步骤 5：优化实现 由于 w 可能范围大，可用哈希表或只记录非负权重状态。 实现时用递推或记忆化搜索，按 i, j 顺序遍历。 举例说明 例： s = "aabc" , t = "aacb" , 权重 a:2, b:-1, c:3, 要求 'a' 必须连续出现 ≥ 2 次。 匹配 "aa" ：从 (0,0,0,0,0) 匹配第一个 'a' → (1,1,2,'a',1) ，第二个 'a' → (2,2,4,'a',2) ，满足连续限制，权重 4。 匹配 "aac" ：续上 'c' → (3,3,7,'c',1) ，但 'a' 段已结束且满足连续限制，合法，权重 7。 匹配 "ac" ：第一个 'a' 后直接接 'c' ， 'a' 段长度 1 < 2，非法。 最大权重为 7（对应子序列 "aac" ）。 总结 本题通过扩展 LCS 状态，加入权重和、连续字符计数，解决了带复杂约束的公共子序列问题。关键在于状态设计能捕获连续出现限制的中间情况，确保最终子序列合法。