最长公共子序列的变种：在两个字符串中分别选取长度相等的子序列，使得对应位置字符相同且子序列的权重和最大
题目描述
给定两个字符串 s 和 t，以及一个字符权重表 weight（例如，字符 'a' 的权重为 1，'b' 的权重为 2 等）。
现在你要从 s 和 t 中各自选取一个长度相同的子序列（不一定要连续，但字符在原始串中顺序必须保留）。
要求这两个子序列在对应位置上的字符相同，并且选取的字符的权重之和最大。
如果不存在这样的子序列，返回 0。
示例
s = "abc", t = "acb", weight[a]=1, weight[b]=2, weight[c]=3
一个可行的选取是：从 s 取 "ab"（位置 1,2），从 t 取 "ab"（位置 1,2）
对应位置字符相同（a 对应 a，b 对应 b），长度均为 2，权重和为 1+2=3。
另一个是取 "ac" 和 "ac"：权重 1+3=4。
最长可行长度是 2，最大权重是 4（取 "ac" 与 "ac"）。
注意不能取长度不同的子序列，必须一一对应。
解题步骤详解
1. 理解问题本质
这是最长公共子序列（LCS）的变种，但有两个额外约束：
- 子序列必须长度相等（在 LCS 中，长度不一定相等，但匹配的字符数量就是结果长度）。
- 每个字符有权重，我们要最大化权重和，而不是长度。
在标准 LCS 中，我们定义 dp[i][j] 为 s[0..i-1] 与 t[0..j-1] 的最长公共子序列长度。
但这里我们要找的是一对长度相等的子序列，并且按顺序匹配，所以匹配的字符数（即子序列长度）是动态决定的，同时权重累加。
2. 定义状态
设 dp[i][j][k] 表示：
考虑 s 的前 i 个字符，t 的前 j 个字符，并且我们选择的公共子序列长度为 k 时，能得到的最大权重和。
- 如果 k=0，权重和为 0（不选任何字符）。
- 如果 s[i-1] == t[j-1]，我们可以考虑将这两个字符匹配，长度 k 加 1，并加上这个字符的权重。
- 如果 s[i-1] != t[j-1]，我们不能匹配这两个字符，只能从 s 少一个字符或 t 少一个字符转移过来，但保持 k 不变。
但这里注意：k 的最大值不会超过 min(len(s), len(t))，且 k 必须从 0 开始逐个增加，因为匹配必须按顺序。
3. 状态转移方程
初始化：dp[0][j][0] = 0，dp[i][0][0] = 0，其他为 -∞（表示不可行）。
转移：
- 不选 s[i-1]：
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) - 不选 t[j-1]：
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]) - 如果 s[i-1] == t[j-1]：
我们可以匹配它们，那么需要从dp[i-1][j-1][k-1]转移过来，并加上weight[s[i-1]]。
即：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + w)，其中 w 是当前字符权重。
注意：只有字符相等时才能增加 k（即增加匹配长度）。
4. 最终答案
最终答案是 max(dp[n][m][k]) 对所有 k 从 1 到 min(n,m) 取最大值。
k 至少为 1 才有意义（因为 k=0 权重和为 0）。
5. 时间复杂度优化
上面 dp 是三维，空间复杂度 O(n×m×min(n,m))，在长度 100 左右可以接受，但更大时可能太大。
可以优化为二维滚动数组吗？
注意：k 只依赖于 k-1 和 i-1,j-1 的状态，所以我们可以用二维 dp[i][j] 表示匹配到当前状态的最大权重和，但这样无法知道我们匹配了多少个字符。不过我们可以换一种定义：
6. 更优的状态定义
定义 dp[i][j] 表示：考虑 s 的前 i 个字符，t 的前 j 个字符，并且我们已经匹配了若干对字符，最后一对匹配的字符是 s[i-1] 与 t[j-1] 时 的最大权重和。
但这样定义会丢失匹配长度信息，而且要求最后一对匹配恰好是 s[i-1] 与 t[j-1]，不便于转移。
更好的二维方法：
设 f[i][j] 表示：从 s[0..i-1] 和 t[0..j-1] 中选取长度相等的公共子序列能达到的最大权重和。
这里的“长度相等公共子序列”是指：存在一个序列 p1<p2<...<pk 来自 s，q1<q2<...<qk 来自 t，使得 s[p] 与 t[q] 一一对应相同，并且我们求最大权重和。
转移：
- 如果不选 s[i-1]：
f[i][j] = max(f[i][j], f[i-1][j]) - 如果不选 t[j-1]：
f[i][j] = max(f[i][j], f[i][j-1]) - 如果 s[i-1] == t[j-1]：
我们可以让这一对匹配，那么就需要找到上一次匹配的位置。
但上一次匹配可能在任意前面的位置。实际上，匹配这一对字符，就相当于在f[i-1][j-1]的基础上，加上这一对新字符的匹配。
然而f[i-1][j-1]是之前的最优解，但可能已经包含了一些匹配，我们添加这一对字符，就增加了一对匹配，但长度增加 1。
但是，如果我们直接加 weight，就相当于认为这两个字符是新匹配的一对，且之前的匹配数任意。
这会导致问题：如果之前的匹配最后一个字符位置是 i-2 和 j-2，那没问题；但如果不是，我们依然可以新增这一对，只要子序列顺序保持。
所以实际上，匹配 s[i-1] 和 t[j-1] 时，可以是从任意前面的状态转移过来，但那样复杂度高。
7. 另一种简洁的二维 DP
定义 dp[i][j] 为：考虑 s[0..i-1] 和 t[0..j-1]，能选出的公共子序列的最大权重和，且这个公共子序列是一一对应匹配的（即长度相等，但长度是隐含的，由匹配对数决定）。
更简单理解：
我们可以将问题转化为：找一个序列 (i1, i2, ..., ik) 和 (j1, j2, ..., jk)，其中 i1 < i2 < ... < ik，j1 < j2 < ... < jk，且 s[ip] = t[jp]，最大化 Σ weight[s[ip]]。
这很像“最长公共子序列”的 DP，但把长度计数换成权重累加，并且要求匹配的字符数（子序列长度）是隐式记录的。
但注意，不要求匹配所有相同字符，只选一部分来最大化权重。
其实可以直接用 LCS 的 DP 改造：
设 dp[i][j] 表示 s[0..i-1] 与 t[0..j-1] 的满足条件的最大权重和。
转移：
- 不选 s[i-1]：
dp[i][j] = max(dp[i][j], dp[i-1][j]) - 不选 t[j-1]：
dp[i][j] = max(dp[i][j], dp[i][j-1]) - 如果 s[i-1] == t[j-1]：我们可以匹配它们，那么
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight[s[i-1]])
但这样会不会重复累加？不会，因为每次匹配字符，就会增加一对匹配，并加上它的权重。
这正好是我们想要的：匹配的字符对数隐含在 dp 值中，因为我们只在相等时才加权重。
这个定义天然保证了子序列长度相等，因为每次匹配就加一个字符对，而且从 i-1, j-1 转移过来，表示之前的匹配在更短的前缀中。
边界：dp[0][j] = 0, dp[i][0] = 0，因为空子序列权重和为 0。
最终答案：dp[n][m]
8. 验证
s = "abc", t = "acb", weight[a]=1,b=2,c=3
i=1(a), j=1(a)：相等，dp[1][1] = max(0, dp[0][0]+1) = 1
i=1(a), j=2(c)：不等，dp[1][2] = max(dp[1][1], dp[0][2]) = 1
i=1(a), j=3(b)：不等，dp[1][3] = max(dp[1][2], dp[0][3]) = 1
i=2(b), j=1(a)：不等，dp[2][1] = max(dp[1][1], dp[2][0]) = 1
i=2(b), j=2(c)：不等，dp[2][2] = max(dp[2][1], dp[1][2]) = 1
i=2(b), j=3(b)：相等，dp[2][3] = max(1, dp[1][2]+2)=max(1,1+2)=3
i=3(c), j=1(a)：不等，dp[3][1] = max(dp[2][1], dp[3][0]) = 1
i=3(c), j=2(c)：相等，dp[3][2] = max(dp[3][1], dp[2][1]+3) = max(1, 1+3)=4
i=3(c), j=3(b)：不等，dp[3][3] = max(dp[3][2], dp[2][3]) = max(4,3)=4
最终 4，对应匹配 ("a","a") 和 ("c","c") 或 ("a","a") 和 ("b","b") 比较权重？实际最优是 ("a","a")+("c","c") 权重 1+3=4。正确。
9. 复杂度
- 时间 O(n×m)
- 空间 O(n×m)，可用滚动数组优化到 O(min(n,m))
总结
这个变种题的核心是：
- 在标准 LCS 的 DP 基础上，将递推中的“长度+1”改为“加权重”。
- 因为只对匹配的字符加权重，自然保证了选取的子序列长度相等（匹配字符对数就是长度）。
- 最终 dp[n][m] 就是最大权重和。