线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现） 题目描述 给定两个字符串 s1 和 s2 ，每个字符有一个权重（可能为负数），要求找到它们的公共子序列，满足： 子序列的权重和（即字符权重之和）非负； 子序列中必须连续出现某个特定子串 pattern （即 pattern 必须是子序列的连续部分）； 允许字符权重为负，但最终权重和需非负。 求满足条件的最长公共子序列的长度及其最大权重和（若权重和相同，取长度更长的子序列）。 解题思路 此题结合了最长公共子序列（LCS）、权重约束、连续子串限制三个难点。我们需要在动态规划状态中记录： 当前匹配到的 s1 和 s2 的位置； 当前已匹配的 pattern 的长度（用于保证连续出现）； 当前权重和（需保证非负）。 步骤详解 状态定义 定义 dp[i][j][k][w] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，已匹配 pattern 的前 k 个字符，且当前权重和为 w 时的最长公共子序列长度。 i 范围：0 到 len(s1) ； j 范围：0 到 len(s2) ； k 范围：0 到 len(pattern) （ k=len(pattern) 表示已完整匹配 pattern ）； w 范围：权重和可能为负，但需限制范围（可通过偏移量处理）。 权重偏移处理 由于权重可能为负，我们将所有权重加上一个足够大的常数 BASE ，使得权重和始终非负，但需注意 BASE 的选择不影响最终结果（因为只关心相对值）。 状态转移 若 s1[i-1] == s2[j-1] ： 当前字符可加入子序列。 更新权重 nw = w + weight[s1[i-1]] 。 对于 pattern 的匹配状态 k ： 如果 k < len(pattern) 且 s1[i-1] == pattern[k] ，则 k 可推进至 k+1 ； 否则 k 保持不变（但需保证 k 不倒退）。 转移方程： dp[i][j][nk][nw] = max(dp[i][j][nk][nw], dp[i-1][j-1][k][w] + 1) 其中 nk 为更新后的 pattern 匹配长度。 若字符不相等 ： 继承 dp[i-1][j][k][w] 或 dp[i][j-1][k][w] 的状态。 初始化和边界 dp[0][0][0][BASE] = 0 （空序列，权重和为 0，偏移后为 BASE ）。 其他状态初始化为负无穷（表示不可达）。 结果提取 遍历所有 i , j ，且 k = len(pattern) （保证 pattern 完整匹配）， w >= BASE （权重和非负），取最大的 dp[i][j][k][w] 。 关键点 通过四维状态同时处理 LCS、连续子串匹配、权重约束； 权重偏移避免负索引； 完整匹配 pattern 后才更新最终结果。 此解法时间复杂度为 O(n²·m·W)，其中 n 为字符串长度，m 为 pattern 长度，W 为权重范围，适用于小规模问题。