线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现） 题目描述 给定两个字符串 s1 和 s2 ，每个字符有一个权重（可能为负数）。要求找到它们的公共子序列，使得该子序列的权重和最大，并且权重和非负。此外，子序列中某些指定字符（如字符 'a'）必须连续出现至少 k 次（例如，子序列中若包含 'a'，则所有 'a' 必须连续出现，不能间断）。求满足条件的最大权重和。 解题过程 问题分析 基础问题是最长公共子序列（LCS）的变种，增加了字符权重、权重和非负的限制，以及某些字符必须连续出现的约束。 难点在于同时处理权重约束和连续性约束，需在动态规划状态中额外记录信息。 状态定义 定义 dp[i][j][w][c] ：考虑 s1 的前 i 个字符和 s2 的前 j 个字符，当前子序列的权重和为 w，且末尾连续字符为 c（c 为特定字符，如 'a'）的连续出现次数。 若 c=0，表示末尾字符不是需连续出现的特定字符。 w 的范围需根据字符权重和字符串长度确定，可通过偏移量处理负权重。 状态转移 若 s1[i-1] == s2[j-1] ，当前字符可加入子序列： 计算新权重 nw = w + weight[ch] 。 若 ch 是需连续出现的字符： 若前状态末尾字符也是 ch，则连续次数 +1。 否则，连续次数置 1。 若 ch 不是需连续字符，连续次数置 0。 仅当 nw >= 0 且连续次数满足要求（如 ≥k）时更新状态。 不选当前字符：从 dp[i-1][j] 或 dp[i][j-1] 转移。 初始化与结果提取 初始化 dp[0][0][0][0] = 0 ，其他为负无穷。 遍历所有状态，取满足连续性约束的最大权重和。 关键点 通过状态中的连续次数记录，确保特定字符连续出现。 权重和通过偏移量映射到非负索引，避免负索引问题。 时间复杂度 O(n²⋅W⋅K)，其中 W 为权重范围，K 为最大连续次数限制。