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

字数 2382 2025-12-23 12:50:29

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

问题描述
给定两个字符串 s1 和 s2，长度分别为 m 和 n。每个字符都有一个正权重，权重存储在数组 w[c] 中（假设字符集为小写字母）。你需要找出一个子序列，它同时是 s1 和 s2 的公共子序列，并且其所有字符的权重之和尽可能大。输出这个最大的权重和。

例如：
s1 = "abcbdab"
s2 = "bdcaba"
权重：w['a']=3, w['b']=2, w['c']=5, w['d']=1（其余字符权重为0）
一个可能的带权公共子序列是 "bcba"（在 s1 中下标为 1,2,4,6；在 s2 中下标为 0,2,3,5），权重和 = 2+5+2+3 = 12。
我们要找到所有公共子序列中权重和最大的那个。

解题思路
这是最长公共子序列（LCS） 的加权推广。经典 LCS 中每个字符的“贡献”是 1，这里每个字符贡献其权重。
我们仍然可以用区间动态规划的思想，只不过“区间”在这里是两个字符串的子串（前缀子问题）。

定义状态：
dp[i][j] 表示考虑 s1 的前 i 个字符（下标 1..i）和 s2 的前 j 个字符（下标 1..j）时，能得到的带权最长公共子序列的最大权重和。
（这里用 1-based 索引方便初始状态，实际编程时注意下标转换）

状态转移方程
我们需要考虑 s1[i] 和 s2[j] 是否相等：

如果 s1[i] == s2[j]（设为字符 c）：
那么这个字符 c 可以选择加入公共子序列，也可以不加入。
- 如果加入，则这个字符贡献权重 w[c]，然后我们需要在 s1[1..i-1] 和 s2[1..j-1] 中找最优解 → dp[i-1][j-1] + w[c]。
- 如果不加入，则相当于忽略这个字符，那么最优解是 dp[i-1][j] 和 dp[i][j-1] 中的较大值吗？
  注意：经典 LCS 中，当 s1[i]==s2[j] 时，我们有 dp[i][j] = dp[i-1][j-1] + 1，但同时我们也可以不考虑它，所以也要比较 dp[i-1][j] 和 dp[i][j-1]。但这里加入权重后，必须考虑“加入”可能比“不加入”更优。
  实际上，状态转移应涵盖三种情况：
  (a) 不使用 s1[i] 和 s2[j] 匹配，但可能用其中一个在别处匹配 → max(dp[i-1][j], dp[i][j-1])。
  (b) 使用 s1[i] 和 s2[j] 匹配 → dp[i-1][j-1] + w[c]。
  所以：
```
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + w[c])
```
如果 s1[i] != s2[j]：
那么它们不能同时作为公共子序列的同一个字符。我们只能从两个方向选最优：
- 不考虑 s1[i]，看 dp[i-1][j]。
- 不考虑 s2[j]，看 dp[i][j-1]。
  所以：
```
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```

注意：dp[i-1][j-1] 在 s1[i]!=s2[j] 时不需要单独比较，因为它已经被 dp[i-1][j] 和 dp[i][j-1] 覆盖（因为 dp[i-1][j] ≥ dp[i-1][j-1] 且 dp[i][j-1] ≥ dp[i-1][j-1]）。

初始化
dp[0][j] = 0 对任意 j，因为 s1 为空时公共子序列为空，权重和为0。
dp[i][0] = 0 同理。

最终答案
dp[m][n]

逐步计算示例
用上面例子，但为简化，假设字符权重同上，我们手动推几步。

s1 = "abcbdab"
s2 = "bdcaba"
权重：a:3, b:2, c:5, d:1

我们建表 dp[7+1][6+1]，索引从0开始，dp[0][]=0, dp[][0]=0。

i=1 (s1[1]='a'), j=1 (s2[1]='b')：'a'!='b'
dp[1][1] = max(dp[0][1]=0, dp[1][0]=0) = 0

i=1, j=2 (s2[2]='d')：'a'!='d'
dp[1][2] = max(dp[0][2]=0, dp[1][1]=0) = 0

… 直到 j=5 (s2[5]='a')：'a'=='a'，权重=3
dp[1][5] = max(dp[0][5]=0, dp[1][4]=0, dp[0][4]+3=3) = 3

i=2 (s1[2]='b'), j=1 (s2[1]='b')：相等，权重=2
dp[2][1] = max(dp[1][1]=0, dp[2][0]=0, dp[1][0]+2=2) = 2

i=2, j=2 (s2[2]='d')：不等
dp[2][2] = max(dp[1][2]=0, dp[2][1]=2) = 2

… 这样递推下去，最终 dp[7][6] 就是答案。

优化思考
这个算法时间复杂度 O(m*n)，空间可以用滚动数组优化到 O(min(m,n))。
如果字符集很小，还可以用 LCS 的其他优化（如转化为最长递增子序列），但这里带权重，经典优化不直接适用。

代码框架（Python）

def weighted_lcs(s1, s2, w):
    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]:
                c = s1[i-1]
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + w[c])
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

总结
带权重 LCS 是 LCS 的自然扩展，只需在状态转移中加入权重项，并小心处理相等时的三种选择（加入匹配、跳过 s1[i]、跳过 s2[j]）。它仍然保持了最优子结构和无后效性，是区间DP在两个序列上的典型应用。

带权重的最长公共子序列（Weighted Longest Common Subsequence）问题描述给定两个字符串 s1 和 s2 ，长度分别为 m 和 n 。每个字符都有一个正权重，权重存储在数组 w[c] 中（假设字符集为小写字母）。你需要找出一个子序列，它同时是 s1 和 s2 的公共子序列，并且其所有字符的权重之和尽可能大。输出这个最大的权重和。例如： s1 = "abcbdab" s2 = "bdcaba" 权重： w['a']=3, w['b']=2, w['c']=5, w['d']=1 （其余字符权重为0）一个可能的带权公共子序列是 "bcba"（在 s1 中下标为 1,2,4,6；在 s2 中下标为 0,2,3,5），权重和 = 2+5+2+3 = 12。我们要找到所有公共子序列中权重和最大的那个。解题思路这是最长公共子序列（LCS）的加权推广。经典 LCS 中每个字符的“贡献”是 1，这里每个字符贡献其权重。我们仍然可以用区间动态规划的思想，只不过“区间”在这里是两个字符串的子串（前缀子问题）。定义状态： dp[i][j] 表示考虑 s1 的前 i 个字符（下标 1..i）和 s2 的前 j 个字符（下标 1..j）时，能得到的带权最长公共子序列的最大权重和。（这里用 1-based 索引方便初始状态，实际编程时注意下标转换）状态转移方程我们需要考虑 s1[i] 和 s2[j] 是否相等：如果 s1[i] == s2[j] （设为字符 c ）：那么这个字符 c 可以选择加入公共子序列，也可以不加入。如果加入，则这个字符贡献权重 w[c] ，然后我们需要在 s1[1..i-1] 和 s2[1..j-1] 中找最优解 → dp[i-1][j-1] + w[c] 。如果不加入，则相当于忽略这个字符，那么最优解是 dp[i-1][j] 和 dp[i][j-1] 中的较大值吗？注意：经典 LCS 中，当 s1[i]==s2[j] 时，我们有 dp[i][j] = dp[i-1][j-1] + 1 ，但同时我们也可以不考虑它，所以也要比较 dp[i-1][j] 和 dp[i][j-1] 。但这里加入权重后，必须考虑“加入”可能比“不加入”更优。实际上，状态转移应涵盖三种情况： (a) 不使用 s1[i] 和 s2[j] 匹配，但可能用其中一个在别处匹配 → max(dp[i-1][j], dp[i][j-1]) 。 (b) 使用 s1[i] 和 s2[j] 匹配 → dp[i-1][j-1] + w[c] 。所以：如果 s1[i] != s2[j] ：那么它们不能同时作为公共子序列的同一个字符。我们只能从两个方向选最优：不考虑 s1[i] ，看 dp[i-1][j] 。不考虑 s2[j] ，看 dp[i][j-1] 。所以：注意： dp[i-1][j-1] 在 s1[i]!=s2[j] 时不需要单独比较，因为它已经被 dp[i-1][j] 和 dp[i][j-1] 覆盖（因为 dp[i-1][j] ≥ dp[i-1][j-1] 且 dp[i][j-1] ≥ dp[i-1][j-1] ）。初始化 dp[0][j] = 0 对任意 j，因为 s1 为空时公共子序列为空，权重和为0。 dp[i][0] = 0 同理。最终答案 dp[m][n] 逐步计算示例用上面例子，但为简化，假设字符权重同上，我们手动推几步。 s1 = "abcbdab" s2 = "bdcaba" 权重：a:3, b:2, c:5, d:1 我们建表 dp[ 7+1][ 6+1]，索引从0开始，dp[ 0][ ]=0, dp[ ][ 0 ]=0。 i=1 (s1[ 1]='a'), j=1 (s2[ 1]='b')：'a' !='b' dp[ 1][ 1] = max(dp[ 0][ 1]=0, dp[ 1][ 0 ]=0) = 0 i=1, j=2 (s2[ 2]='d')：'a' !='d' dp[ 1][ 2] = max(dp[ 0][ 2]=0, dp[ 1][ 1 ]=0) = 0 … 直到 j=5 (s2[ 5 ]='a')：'a'=='a'，权重=3 dp[ 1][ 5] = max(dp[ 0][ 5]=0, dp[ 1][ 4]=0, dp[ 0][ 4 ]+3=3) = 3 i=2 (s1[ 2]='b'), j=1 (s2[ 1 ]='b')：相等，权重=2 dp[ 2][ 1] = max(dp[ 1][ 1]=0, dp[ 2][ 0]=0, dp[ 1][ 0 ]+2=2) = 2 i=2, j=2 (s2[ 2 ]='d')：不等 dp[ 2][ 2] = max(dp[ 1][ 2]=0, dp[ 2][ 1 ]=2) = 2 … 这样递推下去，最终 dp[ 7][ 6 ] 就是答案。优化思考这个算法时间复杂度 O(m* n)，空间可以用滚动数组优化到 O(min(m,n))。如果字符集很小，还可以用 LCS 的其他优化（如转化为最长递增子序列），但这里带权重，经典优化不直接适用。代码框架（Python）总结带权重 LCS 是 LCS 的自然扩展，只需在状态转移中加入权重项，并小心处理相等时的三种选择（加入匹配、跳过 s1[ i]、跳过 s2[ j ]）。它仍然保持了最优子结构和无后效性，是区间DP在两个序列上的典型应用。