最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重） 题目描述 给定两个字符串 text1 和 text2 ，以及一个权重映射表，记录每个字符的权重值（权重可以是正数、负数或零）。要求找到 text1 和 text2 的一个公共子序列，使得该子序列中所有字符的权重之和最大。输出这个最大的权重和。 示例 输入： text1 = "abc", text2 = "acb" 权重映射：a: 2, b: -1, c: 3 输出：5 解释：公共子序列 "ac" 的权重和为 2 + 3 = 5（子序列 "ab" 的权重和为 2 + (-1) = 1，子序列 "ac" 是最优解）。 解题过程 定义状态 设 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符形成的所有公共子序列的最大权重和。 状态转移方程 若 text1[i-1] == text2[j-1] （字符匹配）： 当前字符的权重为 weight ，则可以选择将该字符加入公共子序列，此时权重和增加 weight ，即 dp[i][j] = dp[i-1][j-1] + weight 。 也可以选择不加入，此时需考虑 dp[i-1][j] 和 dp[i][j-1] 的情况。 因此转移方程为： dp[i][j] = max(dp[i-1][j-1] + weight, dp[i-1][j], dp[i][j-1]) 若字符不匹配： 当前字符不能同时加入公共子序列，因此从 dp[i-1][j] 和 dp[i][j-1] 中取最大值： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 初始化 当 i = 0 或 j = 0 时，一个字符串为空，公共子序列权重和为 0： dp[0][j] = 0 ， dp[i][0] = 0 计算顺序 从小到大遍历 i 和 j （ i 从 1 到 len(text1) ， j 从 1 到 len(text2) ）。 最终结果 结果为 dp[len(text1)][len(text2)] 。 举例说明 以示例 text1 = "abc", text2 = "acb" 为例： 权重：a:2, b:-1, c:3 构建 dp 表（行列分别对应 text1 和 text2 的字符索引，空白处初始为 0）： | | "" | a | c | b | |-------|----|---|---|---| | "" | 0 | 0 | 0 | 0 | | a | 0 | 2 | 2 | 2 | | b | 0 | 2 | 2 | 1 | | c | 0 | 2 | 5 | 5 | 计算过程： i=1, j=1 ：字符 'a' 匹配，权重 2， dp[1][1] = max(0+2, 0, 0) = 2 i=1, j=2 ：'a'≠'c'，取 max(0, 2) = 2 i=1, j=3 ：'a'≠'b'，取 max(0, 2) = 2 i=2, j=1 ：'b'≠'a'，取 max(2, 0) = 2 i=2, j=2 ：'b'≠'c'，取 max(2, 2) = 2 i=2, j=3 ：'b' 匹配，权重 -1， dp[2][3] = max(2 + (-1), 2, 2) = 1 i=3, j=1 ：'c'≠'a'，取 max(2, 0) = 2 i=3, j=2 ：'c' 匹配，权重 3， dp[3][2] = max(2 + 3, 2, 2) = 5 i=3, j=3 ：'c'≠'b'，取 max(5, 1) = 5 最终结果 dp[3][3] = 5 ，符合示例。