最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重） 题目描述 给定两个字符串s和t，以及一个权重函数w，该函数为每个字符分配一个整数权重（可能为正、负或零）。我们需要找到s和t的一个公共子序列，使得该子序列中所有字符的权重之和最大。注意，子序列不要求连续，但必须保持字符在原字符串中的相对顺序。 例如： s = "ABC", t = "ACB", 权重函数：w('A')=2, w('B')=-1, w('C')=1 可能的公共子序列有："A"（权重2），"B"（权重-1），"C"（权重1），"AB"（权重2+(-1)=1），"AC"（权重2+1=3），"BC"（权重-1+1=0），"ABC"（权重2+(-1)+1=2）。 最大权重公共子序列是"AC"，权重和为3。 解题过程 问题分析 这是最长公共子序列（LCS）问题的变种，但目标从最大化子序列长度变为最大化子序列的权重和。 关键点：权重可以是负数，这意味着我们可能不希望包含某些权重为负的字符，即使它们能形成公共子序列。 定义状态 令 dp[i][j] 表示字符串s的前i个字符（s[ 0..i-1]）和字符串t的前j个字符（t[ 0..j-1 ]）所形成的所有公共子序列中，最大的权重和。 注意： dp[i][j] 可能为负数，因为权重允许为负。 状态转移方程 我们需要考虑如何从已知状态推导出 dp[i][j] 。 情况1 ：不考虑s的第i个字符（即s[ i-1]）。那么最大权重和就是 dp[i-1][j] 。 情况2 ：不考虑t的第j个字符（即t[ j-1]）。那么最大权重和就是 dp[i][j-1] 。 情况3 ：如果s[ i-1]等于t[ j-1]，那么我们可以考虑让这个字符成为公共子序列的一部分。此时，最大权重和是 dp[i-1][j-1] + w(s[i-1]) 。 但是，由于权重可能为负，我们还需要考虑一个情况：即使字符匹配，如果 w(s[i-1]) 是负数，并且 dp[i-1][j-1] 也是负数，那么加上这个字符可能不如一个空的公共子序列（权重和为0）。因此，我们需要确保状态值不会因为添加负权重的匹配而变得不必要地小。然而，在我们的定义中， dp[i][j] 本身就允许为负，它表示的是“最大”权重和，所以当 dp[i-1][j-1] + w(s[i-1]) 为负数时，它可能不是最优解，因为我们可以选择不匹配任何字符（即公共子序列为空，权重和为0）。但请注意，我们的状态 dp[i][j] 是允许包含空子序列的（权重和为0），因为初始状态 dp[0][0]=0 。在状态转移中，我们通过取最大值来确保总是选择最优解。 综合以上情况，状态转移方程为： 如果s[ i-1] == t[ j-1 ]: dp[i][j] = max(0, dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + w(s[i-1])) 这里引入0，是考虑空子序列的情况。因为空子序列的权重和为0，可能比某些负数的权重和更大。 如果s[ i-1] != t[ j-1 ]: dp[i][j] = max(0, dp[i-1][j], dp[i][j-1]) 另一种更简洁的写法是，始终考虑空子序列的可能性，即： dp[i][j] = max(0, dp[i-1][j], dp[i][j-1]) 如果s[ i-1] == t[ j-1]，再比较 max(dp[i][j], dp[i-1][j-1] + w(s[i-1])) 初始化 dp[0][0] = 0 ：两个空字符串的公共子序列只有空序列，权重和为0。 对于i>0， dp[i][0] = 0 ：字符串s的前i个字符和空字符串t的公共子序列只有空序列。 对于j>0， dp[0][j] = 0 ：空字符串s和字符串t的前j个字符的公共子序列只有空序列。 计算顺序 由于计算 dp[i][j] 需要用到 dp[i-1][j] 、 dp[i][j-1] 和 dp[i-1][j-1] ，我们按照i从0到len(s)，j从0到len(t)的顺序进行双重循环计算即可。 最终结果 最终结果就是 dp[len(s)][len(t)] ，它代表了s和t的所有公共子序列中最大的权重和。 举例验证 以s="ABC", t="ACB"为例，权重w('A')=2, w('B')=-1, w('C')=1。 构建dp表，大小为(4)x(4)（因为字符串长度都是3，加上空串情况）。 初始化第一行和第一列为0。 计算过程： i=1, j=1: s[ 0]='A', t[ 0]='A'，匹配。 dp[1][1] = max(0, dp[0][1]=0, dp[1][0]=0, dp[0][0]+2=0+2=2) = 2 i=1, j=2: s[ 0]='A', t[ 1]='C'，不匹配。 dp[1][2] = max(0, dp[0][2]=0, dp[1][1]=2) = 2 i=1, j=3: s[ 0]='A', t[ 2]='B'，不匹配。 dp[1][3] = max(0, dp[0][3]=0, dp[1][2]=2) = 2 i=2, j=1: s[ 1]='B', t[ 0]='A'，不匹配。 dp[2][1] = max(0, dp[1][1]=2, dp[2][0]=0) = 2 i=2, j=2: s[ 1]='B', t[ 1]='C'，不匹配。 dp[2][2] = max(0, dp[1][2]=2, dp[2][1]=2) = 2 i=2, j=3: s[ 1]='B', t[ 2]='B'，匹配。 dp[2][3] = max(0, dp[1][3]=2, dp[2][2]=2, dp[1][2] + w('B')=2+(-1)=1) = 2 (因为2>1) i=3, j=1: s[ 2]='C', t[ 0]='A'，不匹配。 dp[3][1] = max(0, dp[2][1]=2, dp[3][0]=0) = 2 i=3, j=2: s[ 2]='C', t[ 1]='C'，匹配。 dp[3][2] = max(0, dp[2][2]=2, dp[3][1]=2, dp[2][1] + w('C')=2+1=3) = 3 i=3, j=3: s[ 2]='C', t[ 2]='B'，不匹配。 dp[3][3] = max(0, dp[2][3]=2, dp[3][2]=3) = 3 最终结果 dp[3][3]=3 ，对应子序列"AC"，验证正确。 复杂度分析 时间复杂度：O(n m)，其中n和m分别是字符串s和t的长度。因为需要填充一个(n+1) (m+1)的DP表。 空间复杂度：O(n* m)。可以优化到O(min(n, m))，如果只使用两行或一维数组进行状态存储。 这个算法有效地解决了带权重（允许负权重）的最长公共子序列问题，确保了在所有可能的公共子序列中找到权重和最大的那个。