最长公共子序列的变种：带字符权重的最长公共子序列

我将为您讲解一个带字符权重的LCS变种问题。这个问题在标准LCS基础上增加了字符权重，要求找到权重和最大的公共子序列。

问题描述
给定两个字符串s和t，以及一个权重函数w(c)为每个字符c赋予一个整数值（可能为负）。求s和t的一个公共子序列，使得该子序列中所有字符的权重之和最大。如果所有可能的公共子序列权重和都为负，则返回0（选择空子序列）。

示例
s = "ABC", t = "ACB"
权重：w(A)=1, w(B)=2, w(C)=3
最大权重公共子序列为"AC"（权重1+3=4）或"AB"（权重1+2=3）或"ACB"（权重1+3+2=6）

解题思路

步骤1：定义状态
定义dp[i][j]表示s的前i个字符和t的前j个字符的最大权重公共子序列的权重和。

步骤2：状态转移方程
考虑三种情况：

1. 不包含s[i]和t[j]：dp[i-1][j-1]
2. 不包含s[i]：dp[i-1][j]
3. 不包含t[j]：dp[i][j-1]
4. 当s[i] == t[j]时，还可以选择包含这个字符：dp[i-1][j-1] + w(s[i])

因此状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
如果s[i] == t[j]，还要比较：max(dp[i][j], dp[i-1][j-1] + w(s[i]))

步骤3：边界条件
dp[0][j] = 0（空字符串与t的前j个字符）
dp[i][0] = 0（s的前i个字符与空字符串）

步骤4：算法实现

def weighted_lcs(s, t, weight_dict):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # 不考虑当前字符的情况
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            
            # 如果字符匹配，考虑包含当前字符的情况
            if s[i-1] == t[j-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight_dict[s[i-1]])
    
    return max(0, dp[m][n])  # 确保结果非负

步骤5：复杂度分析

• 时间复杂度：O(mn)，需要填充m×n的DP表
• 空间复杂度：O(mn)，可以优化到O(min(m,n))

步骤6：处理负权重情况
由于权重可能为负，我们需要确保最终结果非负。在返回时与0取最大值，表示可以选择空子序列。

实例验证
用之前的例子：s="ABC", t="ACB", 权重A=1,B=2,C=3

DP表填充过程：

• i=1,j=1: s[0]='A', t[0]='A'匹配，dp[1][1]=max(0,0,0,0+1)=1
• i=1,j=2: s[0]='A', t[1]='C'不匹配，dp[1][2]=max(1,0)=1
• i=1,j=3: s[0]='A', t[2]='B'不匹配，dp[1][3]=max(1,0)=1
• i=2,j=1: s[1]='B', t[0]='A'不匹配，dp[2][1]=max(0,1)=1
• i=2,j=2: s[1]='B', t[1]='C'不匹配，dp[2][2]=max(1,1)=1
• i=2,j=3: s[1]='B', t[2]='B'匹配，dp[2][3]=max(1,1,1,1+2)=3
• i=3,j=1: s[2]='C', t[0]='A'不匹配，dp[3][1]=max(1,0)=1
• i=3,j=2: s[2]='C', t[1]='C'匹配，dp[3][2]=max(1,1,1,1+3)=4
• i=3,j=3: s[2]='C', t[2]='B'不匹配，dp[3][3]=max(4,3)=4

最终结果：max(0,4)=4，与预期一致。

这个算法优雅地处理了字符权重，是标准LCS问题的有意义的扩展。