线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重）

题目描述
给定两个字符串s和t，以及一个字符权重映射表weight，其中weight[c]表示字符c的权重（可以是正数、负数或零）。我们需要找到s和t的一个公共子序列，使得该子序列中所有字符的权重之和最大。如果不存在公共子序列，返回0。

解题思路
这个问题是最长公共子序列（LCS）的变种，但目标不是最大化子序列长度，而是最大化子序列的权重和。由于权重可以是负数，我们需要仔细设计状态转移方程。

详细解题步骤

1. 定义状态
   定义dp[i][j]为字符串s的前i个字符和字符串t的前j个字符的最大权重公共子序列的权重和。

2. 状态初始化

   • 当i=0或j=0时，表示其中一个字符串为空，此时公共子序列为空，权重和为0。
   • 因此，dp[0][j] = 0 (0 ≤ j ≤ len(t))
   • dp[i][0] = 0 (0 ≤ i ≤ len(s))

3. 状态转移方程
   对于每个位置(i, j)，我们考虑三种情况：

   • 不包含s的第i个字符：dp[i][j] = dp[i-1][j]
   • 不包含t的第j个字符：dp[i][j] = dp[i][j-1]
   • 如果s[i-1] == t[j-1]，我们可以选择包含这个字符：dp[i][j] = dp[i-1][j-1] + weight[s[i-1]]

   我们需要取这三种情况的最大值：
   dp[i][j] = max(dp[i-1][j], dp[i][j-1],
   (如果s[i-1] == t[j-1]则 dp[i-1][j-1] + weight[s[i-1]] else -∞))

4. 处理负权重
   由于权重可以是负数，我们需要确保：

   • 当选择包含字符时，只有当dp[i-1][j-1] + weight[s[i-1]] > 当前已知最大值时才更新
   • 如果这个值小于0，我们仍然可以选择它，因为可能没有更好的选择

5. 最终结果
   最终答案是dp[len(s)][len(t)]，即考虑整个字符串s和t时的最大权重和。

示例演示
假设s = "abc", t = "ac", weight = {'a': 2, 'b': -1, 'c': 3}

构建dp表：

   ""  "a"  "ac"
""  0    0    0
"a" 0    2    2
"ab"0    2    2  
"abc"0   2    5

计算过程：

• dp[1][1]: s[0]='a'=t[0]='a' → max(0, 0, 0+2)=2
• dp[1][2]: s[0]='a'≠t[1]='c' → max(2, 0, -∞)=2
• dp[2][1]: s[1]='b'≠t[0]='a' → max(0, 2, -∞)=2
• dp[2][2]: s[1]='b'≠t[1]='c' → max(2, 2, -∞)=2
• dp[3][1]: s[2]='c'≠t[0]='a' → max(2, 0, -∞)=2
• dp[3][2]: s[2]='c'=t[1]='c' → max(2, 2, 2+3)=5

最大权重公共子序列是"ac"，权重和为2+3=5。

复杂度分析

• 时间复杂度：O(m×n)，其中m和n分别是字符串s和t的长度
• 空间复杂度：O(m×n)，可以使用滚动数组优化到O(min(m,n))

这个算法通过动态规划有效地解决了带权重的最长公共子序列问题，即使权重为负也能正确处理。