最长公共子序列的变种：在两个字符串中分别选取长度相等的子序列，使得对应位置字符相同且子序列的权重和最大

题目描述

给定两个字符串 text1 和 text2，长度分别为 n 和 m。我们可以在 text1 中选取一个子序列 A，在 text2 中选取一个子序列 B，要求：

1. A 和 B 长度相等，设为 L。
2. 对于所有 i（1 ≤ i ≤ L），A[i] = B[i]（对应位置的字符相同）。
3. 每个字符 ch 有一个权重 w[ch]（可以是正数、负数或零）。

目标是选择这样的 A 和 B，使得 ∑ w[A[i]]（即子序列所有字符的权重和）最大。输出这个最大权重和。

注意：子序列不要求连续，但必须保持原有顺序，且两个子序列长度必须严格相等。

思路分析

这是一个线性动态规划问题，与经典 LCS（最长公共子序列）问题相似，但有以下不同：

• 不要求子序列尽可能长，而是要求权重和最大。
• 子序列必须长度相等，且对应位置字符匹配。

我们如何设计状态？
设 dp[i][j] 表示：考虑 text1[0..i-1] 和 text2[0..j-1]，已经匹配了一定长度的相等子序列，但是这样定义并不直接，因为我们需要同时记录匹配长度和权重和。

更自然的方式：
定义 dp[i][j] 为：从 text1 的前 i 个字符和 text2 的前 j 个字符中，选取长度相等且对应位置相同的子序列，能得到的最大权重和。

状态转移方程推导

考虑 text1[i-1] 和 text2[j-1]（注意字符串下标从0开始，dp下标从1开始）：

• 如果 text1[i-1] == text2[j-1]，那么我们可以将这个字符加入匹配子序列中，此时：

  dp[i][j] = max(dp[i-1][j-1] + w[ch], dp[i-1][j], dp[i][j-1])
  

  解释：

  1. dp[i-1][j-1] + w[ch]：匹配当前字符，权重增加 w[ch]。
  2. dp[i-1][j]：不使用 text1[i-1]。
  3. dp[i][j-1]：不使用 text2[j-1]。
     注意：dp[i-1][j] 和 dp[i][j-1] 可能已经包含一些匹配，但这样转移能否保证子序列长度相等？
     实际上，dp[i-1][j] 可能匹配了 text1 的前 i-1 与 text2 的前 j 中的某些字符，如果当前字符不匹配，不能直接取，因为那样可能导致长度不等？

  仔细思考：我们的定义是“已经选取的子序列长度相等”，那么如果 text1[i-1] != text2[j-1]，我们不能同时选取它们，但我们可以选择跳过其中一个。但是跳过其中一个会导致长度不等吗？
  不对——如果我们跳过 text1[i-1]，那么意味着我们在 text1[0..i-1] 和 text2[0..j] 中选取的子序列长度相等，这是合法的，因为 text2[j] 不一定被选。同理跳过 text2[j-1] 也合法。

  但如果 text1[i-1] == text2[j-1]，我们可以选择：

  • 匹配它们（长度都+1，权重增加）。
  • 不匹配它们（跳过其中一个或两个）。

因此状态转移方程修正为：

if text1[i-1] == text2[j-1]:
    dp[i][j] = max(dp[i-1][j-1] + w[ch], dp[i-1][j], dp[i][j-1])
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

但是这样对吗？考虑一个例子：
text1 = "a", text2 = "a", w['a'] = -5。
显然，选取子序列 "a" 和 "a" 权重为 -5，而不选取（空子序列）权重为 0，所以最优是 0。
按照上面的方程：
dp[1][1] = max(dp[0][0] + (-5), dp[0][1], dp[1][0]) = max(-5, 0, 0) = 0 ✔

再考虑 w['a'] = 10：
dp[1][1] = max(0 + 10, 0, 0) = 10 ✔

初始化

dp[0][j] 表示 text1 空串，text2 前 j 个字符：只能选空子序列，权重和 = 0。
dp[i][0] 同理。
所以 dp[i][0] = dp[0][j] = 0。

最终答案

dp[n][m] 就是最大权重和，允许空子序列（权重和 = 0）。

算法步骤

1. 输入 text1（长度 n），text2（长度 m），以及权重数组 w（字典或数组映射字符到整数）。
2. 初始化 dp 为 (n+1) x (m+1) 的二维数组，全部设为 0。
3. 遍历 i 从 1 到 n，遍历 j 从 1 到 m：
   • 如果 text1[i-1] == text2[j-1]：
     ch = text1[i-1]
dp[i][j] = max(dp[i-1][j-1] + w[ch], dp[i-1][j], dp[i][j-1])
   • 否则：
     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. 输出 dp[n][m]。

举例验证

例1

text1 = "abc"
text2 = "acb"
w = {'a': 1, 'b': 2, 'c': -1}

dp 表（i 行 j 列）：

• 初始化第一行第一列全 0。
• i=1,j=1: 'a'=='a' → dp[1][1] = max(0+1,0,0)=1
• i=1,j=2: 'a'!='c' → dp[1][2] = max(1,0)=1
• i=1,j=3: 'a'!='b' → dp[1][3] = max(1,0)=1
• i=2,j=1: 'b'!='a' → dp[2][1] = max(1,0)=1
• i=2,j=2: 'b'!='c' → dp[2][2] = max(1,1)=1
• i=2,j=3: 'b'=='b' → dp[2][3] = max(1+2, 1, 1) = 3
• i=3,j=1: 'c'!='a' → dp[3][1] = max(1,0)=1
• i=3,j=2: 'c'=='c' → dp[3][2] = max(1 + (-1), 3, 1) = max(0,3,1)=3
• i=3,j=3: 'c'!='b' → dp[3][3] = max(3,3)=3

最终结果 = 3。
解释：选取 "ab" 与 "ab"（text1 中索引0,1，text2 中索引0,2）权重=1+2=3。

例2（全负权重）

text1 = "aa"
text2 = "aa"
w = {'a': -5}

dp 表：

• i=1,j=1: 匹配 → max(0 + (-5), 0, 0) = 0
• i=1,j=2: 'a'=='a' → max(0 + (-5), 0, 0) = 0
• i=2,j=1: 同上 → 0
• i=2,j=2: 匹配 → max(0 + (-5), 0, 0) = 0
  结果=0（空子序列）。

时间复杂度

O(nm)，空间 O(nm)，可优化为 O(min(n,m)) 滚动数组。

边界情况

• 字符串为空 → 结果为 0。
• 所有权重为负 → 结果为 0（选空子序列）。
• 字符集较大时，权重通过字典映射。

这个变种问题强调了权重优化而非长度优化，但保持了子序列匹配的核心，是 LCS 类问题的一个实用扩展。