线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重） 题目描述： 给定两个字符串s1和s2，每个字符都有一个权重值（权重可以是正数、负数或零）。要求找到s1和s2的一个公共子序列，使得该子序列中所有字符的权重之和最大。注意：子序列不要求连续，但必须保持原始顺序。 解题过程： 步骤1：问题分析 这是最长公共子序列（LCS）的加权版本，但目标从最大化长度变为最大化权重和 关键点：权重可为负，因此不能简单地将LCS中的计数改为累加权重 需要处理负权重情况：当权重为负时，我们可能不希望包含某些字符 步骤2：定义状态 令dp[ i][ j ]表示s1的前i个字符和s2的前j个字符的最大权重公共子序列的权重和 i的范围是0到len(s1)，j的范围是0到len(s2) 步骤3：状态转移方程 情况1：当i=0或j=0时（空字符串） dp[ 0][ j ] = 0（空字符串与任何字符串的公共子序列权重和为0） dp[ i][ 0 ] = 0 情况2：当s1[ i-1] = s2[ j-1 ]时（字符匹配） 我们可以选择包含或不包含这个匹配的字符 如果包含：dp[ i][ j] = dp[ i-1][ j-1] + weight(s1[ i-1 ]) 如果不包含：考虑dp[ i-1][ j]或dp[ i][ j-1 ] 但由于权重可能为负，我们需要比较所有可能性： dp[ i][ j] = max(dp[ i-1][ j-1] + weight(s1[ i-1]), dp[ i-1][ j], dp[ i][ j-1 ], 0) 情况3：当s1[ i-1] ≠ s2[ j-1 ]时（字符不匹配） 只能考虑跳过s1的当前字符或s2的当前字符： dp[ i][ j] = max(dp[ i-1][ j], dp[ i][ j-1 ], 0) 步骤4：初始化细节 将dp表初始化为0 特别注意：当权重和为负时，我们可以选择空子序列（权重和为0） 步骤5：算法实现 创建二维数组dp，大小为(len(s1)+1) × (len(s2)+1) 初始化第一行和第一列为0 遍历i从1到len(s1)，遍历j从1到len(s2)： 如果s1[ i-1] == s2[ j-1 ]： dp[ i][ j] = max(dp[ i-1][ j-1] + weight, dp[ i-1][ j], dp[ i][ j-1 ], 0) 否则： dp[ i][ j] = max(dp[ i-1][ j], dp[ i][ j-1 ], 0) 最终结果是dp[ len(s1)][ len(s2) ] 步骤6：示例演示 假设s1 = "AB", s2 = "BA"，权重：A=2, B=-1 构建dp表： "" B A "" 0 0 0 A 0 0 2 B 0 -1 2 解释： dp[ 1][ 1 ]：s1="A", s2="B"，不匹配，取max(0,0,0)=0 dp[ 1][ 2 ]：s1="A", s2="BA"，匹配A，max(0+2,0,2,0)=2 dp[ 2][ 1 ]：s1="AB", s2="B"，匹配B，max(0+(-1),0,0,0)=0 dp[ 2][ 2 ]：s1="AB", s2="BA"，匹配B但权重为负，取max(0,2,0,0)=2 步骤7：复杂度分析 时间复杂度：O(mn)，其中m和n分别是s1和s2的长度 空间复杂度：O(mn)，可优化到O(min(m,n)) 步骤8：边界情况处理 空字符串输入 所有权重都为负（最佳选择是空子序列） 所有权重都为正（退化为加权LCS） 字符串长度差异很大时的优化