线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现k次）

题目描述

给定两个字符串s和t，每个字符都有一个权重（可能为正、负或零）。要求找到s和t的一个公共子序列，满足：

1. 子序列的权重和（即所有字符权重之和）非负
2. 子序列中某些特定字符（给定集合）必须连续出现至少k次
3. 在满足前两个条件的前提下，使子序列的权重和最大化

解题思路

步骤1：定义状态

设dp[i][j][c][cnt]表示考虑s的前i个字符和t的前j个字符时，以字符c结尾且该字符已连续出现cnt次的情况下，能获得的最大权重和。

由于需要处理字符连续出现的约束，我们需要记录：

• 当前子序列的最后一个字符是什么
• 这个字符已经连续出现了多少次

步骤2：状态转移方程

情况1：不选择当前字符

dp[i][j][c][cnt] = max(
    dp[i-1][j][c][cnt],  // 不考虑s[i]
    dp[i][j-1][c][cnt]   // 不考虑t[j]
)

情况2：选择当前字符（仅当s[i] = t[j]时）
设当前字符为ch = s[i] = t[j]

如果ch == c（与上一个字符相同）：

dp[i][j][ch][cnt] = max(
    dp[i][j][ch][cnt],
    dp[i-1][j-1][ch][cnt-1] + weight[ch]  // 延续之前的连续序列
)

如果ch != c（与上一个字符不同）：

dp[i][j][ch][1] = max(
    dp[i][j][ch][1],
    dp[i-1][j-1][c'][cnt'] + weight[ch]  // 对所有可能的c', cnt'
)

步骤3：处理约束条件

约束1：权重和非负
在状态转移过程中，如果某个状态的权重和变为负数，我们可以直接跳过该状态，因为后续无论如何添加字符，权重和都不会变得更好。

约束2：特定字符必须连续出现至少k次
对于特定字符集合中的字符，只有当cnt >= k时，该状态才是合法的。我们可以在最终答案中只考虑满足这一条件的状态。

步骤4：初始化

dp[0][0][c][0] = 0  // 空序列，权重和为0
其他状态初始化为负无穷

步骤5：最终答案

最终答案是所有满足条件的dp[n][m][c][cnt]中的最大值，其中：

• 权重和 ≥ 0
• 如果c是特定字符，则cnt ≥ k

举例说明

假设：

• s = "aabb", t = "abab"
• 权重：a=2, b=-1
• 特定字符：{'a'}，要求连续出现至少2次
• k = 2

计算过程：

1. 初始化：dp[0][0][*][0] = 0

2. i=1,j=1: s[0]='a', t[0]='a'

   • 匹配，选择'a'
   • dp[1][1]['a'][1] = 2

3. i=2,j=2: s[1]='a', t[1]='b'

   • 不匹配，考虑跳过s[1]或t[1]
   • 跳过t[1]: dp[2][1]['a'][1] = 2

4. i=2,j=3: s[1]='a', t[2]='a'

   • 匹配，选择'a'
   • 延续之前的'a': dp[2][3]['a'][2] = 2 + 2 = 4

5. 继续处理剩余字符...

最终找到满足条件的子序列"aa"（连续出现2次'a'），权重和为4。

优化技巧

1. 空间优化：由于状态只依赖于前一行和前一列，可以使用滚动数组优化空间复杂度。

2. 剪枝：当权重和变为负数时立即剪枝，因为后续添加字符不会使结果变好。

3. 预处理：可以预处理特定字符的信息，加速约束条件的检查。

这个算法的时间复杂度为O(n×m×|Σ|×k)，其中|Σ|是字符集大小，在实际应用中通常是可接受的。