最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现k次） 题目描述 给定两个字符串 s 和 t ，以及一个字符权重数组 w ，其中 w[c] 表示字符 c 的权重（可能为负数）。要求找到一个 s 和 t 的公共子序列，使得： 子序列的权重和（即所有字符权重的总和）非负。 子序列中某些指定字符（例如字符 'a' ）必须连续出现至少 k 次（如果出现的话）。 在满足上述条件的前提下，子序列的长度尽可能长。 解题思路 这是一个带有多重限制的公共子序列问题。我们需要在传统最长公共子序列（LCS）的动态规划基础上，增加状态来记录权重和以及连续字符的出现次数。 状态定义 定义 dp[i][j][weight][cnt] 表示考虑字符串 s 的前 i 个字符和 t 的前 j 个字符时，当前子序列的权重和为 weight ，且最后一个字符（如果是指定字符）已连续出现 cnt 次时的最长公共子序列长度。 状态转移 不选当前字符 ：直接继承之前的状态。 dp[i][j][weight][cnt] = max(dp[i][j][weight][cnt], dp[i-1][j][weight][cnt], dp[i][j-1][weight][cnt]) 当 s[i-1] == t[j-1] 时 ，考虑选择当前字符 c = s[i-1] ： 计算新权重 new_weight = weight + w[c] 。 如果 c 是指定字符，更新连续计数 new_cnt = cnt + 1 ；否则 new_cnt = 0 。 如果 new_weight >= 0 且 new_cnt 满足连续出现要求（即如果 c 是指定字符，则 new_cnt >= k 或 new_cnt == 0 ），则更新状态： dp[i][j][new_weight][new_cnt] = max(dp[i][j][new_weight][new_cnt], dp[i-1][j-1][weight][cnt] + 1) 边界条件 初始时 dp[0][0][0][0] = 0 ，其他为负无穷。 权重范围需要根据字符权重和字符串长度确定上下界。 最终答案 遍历所有可能的权重和非负，以及连续计数满足条件的状态，取最大值。 复杂度分析 时间复杂度：O(n m W* K)，其中 W 是权重范围，K 是最大连续计数。 空间复杂度：O(n m W* K)，可通过滚动数组优化。 这个解法通过增加状态维度，灵活处理了权重和连续字符的限制，确保了在复杂约束下仍能找到最优解。