线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现k次） 题目描述 给定两个字符串 s1 和 s2 ，每个字符 c 有一个权重 w(c) （可能为负数）。要求找到 s1 和 s2 的一个公共子序列，满足： 子序列的权重和（即所有字符权重的总和）非负； 若子序列中某字符 c 出现，则必须连续出现至少 k 次（ k 为给定常数）； 子序列的长度尽可能长，且权重和尽可能大（优先保证长度最长，其次权重和最大）。 例如： s1 = "aabbbcc" , s2 = "aabcc" , k = 2 ，权重 w(a)=1, w(b)=-1, w(c)=2 。 有效子序列： "aabbcc" （需检查连续出现条件）或 "aacc" （若 'a' 仅出现1次则无效）。 解题思路 此问题结合了 LCS 的匹配逻辑、权重约束和连续出现限制。需设计状态记录当前匹配位置、权重和、以及最近字符的连续出现次数。 步骤详解 1. 状态定义 设 dp[i][j][t][ch] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符，当前子序列末尾字符为 ch （ ch=0 表示空，否则为字符索引），且该字符已连续出现 t 次（ t ≥ 0 ）时，能得到的最大长度（或记录权重和）。 但直接记录权重和会导致状态空间过大（权重和可能为负且范围广）。因此调整： 优先最大化长度，其次最大化权重和。可设计为二元组 (len, weight) 作为状态值，比较时先比 len 再比 weight 。 连续出现限制：当 t > 0 时，若新字符与 ch 相同，则 t 增加；否则需检查 t ≥ k 才允许切换字符。 2. 状态转移 分情况讨论： 不选当前字符 ：直接继承 dp[i-1][j][t][ch] 或 dp[i][j-1][t][ch] 。 选当前字符 （需 s1[i] = s2[j] ）： 若 ch = 0 （空子序列）：新增字符，长度+1，权重增加 w(ch) ，连续次数 t=1 。 若 ch = s1[i] ：延续当前字符， t 加 1，长度+1，权重增加 w(ch) 。 若 ch ≠ s1[i] 且 t ≥ k ：可切换字符，新字符连续次数 t=1 ，长度+1，权重增加 w(ch) 。 若 ch ≠ s1[i] 且 t < k ：不允许切换（违反连续出现限制）。 3. 权重非负约束 在状态转移过程中，若某状态的权重和变为负数，可直接丢弃（因为后续增加字符可能使权重更小，且题目要求非负）。但需注意：最终状态权重非负，中间状态允许负权重（因后续可能加正权字符）。因此不能简单剪枝，需保留所有可能的状态。 4. 优化策略 状态数： O(n² * T * C) ，其中 T 为最大连续次数（可限制为 k 以上，因超过 k 后只需记录 t≥k ）， C 为字符集大小。 使用滚动数组减少空间复杂度。 初始化： dp[0][j][0][0] = (0,0) ，表示空子序列。 5. 最终答案 遍历所有 i=|s1|, j=|s2| 的状态，找出满足 t≥k 或 t=0 且权重和非负的最大 (len, weight) 。 举例说明 设 s1="aab", s2="ab", k=2, w(a)=1, w(b)=1 。 有效子序列需字符连续出现至少2次。 公共子序列有 "a" （无效，因 'a' 仅1次）、 "b" （无效）、 "ab" （无效）、 "aab" （ s2 中无足够 'a' ），故无解。 若 s2="aab" ，则 "aab" 有效（ 'a' 连续2次）。 通过以上步骤，可系统解决带权重和连续出现限制的 LCS 变种问题。