最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重） 题目描述： 给定两个字符串s和t，以及一个权重函数w，该函数为每个字符对(c1, c2)分配一个权重值。当c1和c2匹配时，我们可以获得相应的权重w(c1, c2)。与标准LCS不同，这里字符匹配可能产生正权重、负权重或零权重。我们的目标是找到一个s和t的公共子序列，使得该子序列中所有匹配字符对的权重之和最大。 解题过程： 问题分析： 这是标准最长公共子序列(LCS)问题的加权变种 关键区别：匹配字符可能带来正收益(正权重)或负收益(负权重) 目标从"最大化子序列长度"变为"最大化权重和" 状态定义： 定义dp[ i][ j ]表示s的前i个字符和t的前j个字符形成的所有公共子序列的最大权重和。 状态转移方程： 对于每个位置(i, j)，我们有三种选择： 不匹配s[ i]：继承dp[ i-1][ j ] 不匹配t[ j]：继承dp[ i][ j-1 ] 匹配s[ i]和t[ j]（当s[ i] = t[ j]时）：dp[ i-1][ j-1] + w(s[ i], t[ j ]) 因此状态转移方程为： dp[ i][ j ] = max( dp[ i-1][ j ], dp[ i][ j-1 ], dp[ i-1][ j-1] + w(s[ i], t[ j]) (当s[ i] = t[ j ]时) ) 边界条件： dp[ 0][ j ] = 0（s为空字符串） dp[ i][ 0 ] = 0（t为空字符串） 算法步骤： 步骤1：初始化dp表，大小为(m+1)×(n+1)，m和n分别为s和t的长度 步骤2：第一行和第一列初始化为0 步骤3：按行遍历i从1到m，按列遍历j从1到n： 计算option1 = dp[ i-1][ j ] 计算option2 = dp[ i][ j-1 ] 如果s[ i-1] == t[ j-1]，计算option3 = dp[ i-1][ j-1] + w(s[ i-1], t[ j-1 ]) dp[ i][ j ] = max(option1, option2, option3) 步骤4：最终结果在dp[ m][ n ] 时间复杂度：O(m×n)，空间复杂度：O(m×n) 关键理解点： 负权重意味着某些匹配可能降低总权重，因此算法需要智能选择是否进行匹配 当权重为负时，最优解可能选择跳过某些匹配 标准LCS是本问题的特例（所有权重为1） 这个算法通过动态规划巧妙地处理了带权重的字符匹配，能够在正负权重混合的情况下找到最优的公共子序列。