带权重的最长公共子序列（Weighted Longest Common Subsequence）

1. 题目描述

给定两个字符串 s1 和 s2，长度分别为 m 和 n。
每个字符都有一个权重（正整数），用数组 weight[c] 表示字符 c 的权重。
我们要寻找一个公共子序列（不必连续），使得这个公共子序列的总权重最大，并返回这个最大总权重。

注意：

• 公共子序列的定义是：它是从 s1 中按原顺序取出一些字符，并从 s2 中按原顺序取出相同字符形成的序列。
• 权重是每个字符单独计算的，即使同一个字符在子序列中出现多次，每次出现都按其权重累加。

示例：

s1 = "abc"
s2 = "acb"
权重：a=5, b=3, c=2

可能的公共子序列包括：

• "a" 权重=5
• "b" 权重=3
• "c" 权重=2
• "ab" 权重=5+3=8（但这里要注意：s1 中有 a 在 b 前，s2 中 a 在 b 前吗？检查 s2 = "acb"，a 在 c 在 b 前，所以 a 和 b 在 s2 中顺序是 a 在 b 前，可以构成 "ab"）
• "ac" 权重=5+2=7（s2 中 a 在 c 前，可以）
• "cb" 权重=2+3=5（s1 中 c 在 b 前，s2 中 c 在 b 前，可以）
• "abc" 权重=5+3+2=10（不行，因为 s2 中顺序是 a,c,b，b 在 c 后面，而 s1 是 a,b,c，公共子序列必须保持原顺序，所以 a,b,c 在 s2 中 b 在 c 后，但 s1 中 b 在 c 前，矛盾，所以 "abc" 不是公共子序列）

实际上最长公共子序列是 "ab" 或 "ac"。
我们要求最大权重：
"ab" 权重=8
"ac" 权重=7
"cb" 权重=5
"a"=5
"b"=3
"c"=2
所以答案是 8。

这个问题是标准 LCS 的带权扩展，在 LCS 的 DP 状态转移中，当两个字符匹配时，不再只是 +1，而是 +weight[c]。

2. 问题分析

标准 LCS 的 DP 定义：
dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度。
状态转移：

• 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

在带权重版本中，长度替换为总权重。
我们需要 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最大权重公共子序列的总权重。

关键：当字符匹配时，我们加入这个字符，它的权重是 weight[s1[i-1]]，所以：
dp[i][j] = dp[i-1][j-1] + weight[s1[i-1]]

当不匹配时，和标准 LCS 一样，取 max(dp[i-1][j], dp[i][j-1])。

初始化：

• 当 i=0 或 j=0 时，公共子序列为空，权重和为 0。

结果：dp[m][n]

3. 递推关系详细推导

设：

• w(c) 表示字符 c 的权重。
• dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最大权重公共子序列的总权重。

情况 1：i=0 或 j=0
此时一个字符串为空，公共子序列只能是空序列，权重和为 0。
所以 dp[0][j] = 0 对任意 j，dp[i][0] = 0 对任意 i。

情况 2：i>0 且 j>0

1. 如果 s1[i-1] == s2[j-1]，我们可以选择将这两个字符加入公共子序列，这样权重增加 w(s1[i-1])，然后看前面的部分 dp[i-1][j-1]。
   所以 dp[i][j] = dp[i-1][j-1] + w(s1[i-1])。
2. 如果 s1[i-1] != s2[j-1]，那么这两个字符不能同时出现在公共子序列中（以它们作为末尾匹配）。
   我们有两种选择：
   • 忽略 s1[i-1]，看 s1[0..i-2] 和 s2[0..j-1] 的匹配：dp[i-1][j]
   • 忽略 s2[j-1]，看 s1[0..i-1] 和 s2[0..j-2] 的匹配：dp[i][j-1]
     取较大者：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

最终答案：dp[m][n]

4. 举例演算

用上面示例：
s1 = "abc"，s2 = "acb"
权重：a=5, b=3, c=2

dp 表大小 (3+1) x (3+1)

初始化：

dp[0][j] = 0
dp[i][0] = 0

填表：
i=1, j=1: s1[0]='a', s2[0]='a' 相等 → dp[1][1] = dp[0][0] + 5 = 5
i=1, j=2: s1[0]='a', s2[1]='c' 不等 → dp[1][2] = max(dp[0][2], dp[1][1]) = max(0,5)=5
i=1, j=3: s1[0]='a', s2[2]='b' 不等 → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0,5)=5

i=2, j=1: s1[1]='b', s2[0]='a' 不等 → dp[2][1] = max(dp[1][1], dp[2][0]) = max(5,0)=5
i=2, j=2: s1[1]='b', s2[1]='c' 不等 → dp[2][2] = max(dp[1][2], dp[2][1]) = max(5,5)=5
i=2, j=3: s1[1]='b', s2[2]='b' 相等 → dp[2][3] = dp[1][2] + 3 = 5+3=8

i=3, j=1: s1[2]='c', s2[0]='a' 不等 → dp[3][1] = max(dp[2][1], dp[3][0]) = max(5,0)=5
i=3, j=2: s1[2]='c', s2[1]='c' 相等 → dp[3][2] = dp[2][1] + 2 = 5+2=7
i=3, j=3: s1[2]='c', s2[2]='b' 不等 → dp[3][3] = max(dp[2][3], dp[3][2]) = max(8,7)=8

所以 dp[3][3] = 8，与前面分析的"ab"权重=8一致。

5. 算法实现

def weighted_lcs(s1, s2, weight):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + weight[s1[i-1]]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# 示例
weight = {'a':5, 'b':3, 'c':2}
s1 = "abc"
s2 = "acb"
print(weighted_lcs(s1, s2, weight))  # 输出 8

时间复杂度：O(mn)
空间复杂度：O(mn)，可优化为 O(n)

6. 常见变体与注意事项

1. 权重可能为负数
   如果权重有负数，那么“不选任何字符”可能是最优的，但本题通常假设权重为正，所以公共子序列越长且包含高权重字符越好。如果权重可负，初始化要注意 dp 从 0 开始，且任何时候 dp 值不会小于 0（如果允许空子序列）。但通常题目会明确权重为正。

2. 如何输出子序列
   和标准 LCS 一样，可以从 dp 表回溯构造出具有最大权重的公共子序列。

3. 多个字符串的带权 LCS
   这是更复杂的版本，需要高维 DP，但本题只涉及两个字符串。

4. 与标准 LCS 的关系
   当所有权重 = 1 时，退化为标准 LCS 的长度。

7. 总结

带权 LCS 是 LCS 的自然扩展，只是将匹配时的 +1 改为 +weight[字符]，状态定义和转移方程几乎一样。
重点在于理解匹配时增加权重，不匹配时沿用之前的最大权重选择。
这个模型可用于生物信息学（序列比对中的加权匹配）、文本相似度加权比较等场景。