最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负） 题目描述 给定两个字符串 s1 和 s2 ，以及一个映射函数 w(c) ，为每个字符 c 分配一个整数权重（可能为负数）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列的字符权重之和最大，并且权重和非负。公共子序列的字符顺序必须与原字符串一致，但不要求连续。 解题过程 问题分析 基础问题是最长公共子序列（LCS），但这里引入了字符权重，且要求权重和最大化并保持非负。 难点在于权重可能为负，需确保子序列的权重和始终非负，同时最大化权重和。 状态定义 设 dp[i][j][k] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，公共子序列的权重和恰好为 k 时的最大长度（或记录是否存在这样的子序列）。 但权重和 k 的范围可能很大（负权重导致负和，正权重导致正和），直接枚举不现实。需调整状态定义。 状态优化 改为： dp[i][j] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，所有可能的公共子序列中，权重和的最大值（但仅记录那些权重和非负的状态）。 但多个子序列可能对应不同权重和，需记录所有可能的非负权重和中的最大值。若权重和可能为负，则忽略（因为要求非负）。 递推方程 初始化： dp[0][j] = 0 和 dp[i][0] = 0 ，表示空子序列的权重和为 0。 若 s1[i-1] == s2[j-1] ： 考虑匹配当前字符，权重增加 w(s1[i-1]) 。新权重和 = 旧权重和 + w(s1[i-1]) 。仅当新权重和非负时更新： dp[i][j] = max(dp[i][j], dp[i-1][j-1] + w(s1[i-1])) 。 无论字符是否匹配，都可跳过 s1 的当前字符或 s2 的当前字符： dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1]) 。 处理负权重 在递推中，若当前权重和加上字符权重后变为负数，则该路径无效（因为要求非负），不更新状态。 最终答案即 dp[n][m] ，其中 n 和 m 为字符串长度。 复杂度优化 直接实现的时间复杂度为 O(nm)，空间复杂度可优化至 O(m) 通过滚动数组。 示例 设 s1 = "ab" , s2 = "ac" ，权重： a: 2 , b: -1 , c: 3 。 公共子序列 "a" 权重和 = 2（非负）。 公共子序列 "ac" 不存在（因字符顺序不一致）。 最终最大权重和为 2。 通过以上步骤，可系统解决带非负约束的加权LCS问题。