最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负） 题目描述 给定两个字符串 s1 和 s2 ，长度分别为 m 和 n 。每个字符 ch 有一个权重 w[ch] （可能为负数）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列的字符权重之和最大，并且权重和必须非负。公共子序列的定义是原字符串中删除某些字符后剩余字符的相对顺序保持不变。 解题过程 状态定义 定义 dp[i][j] 为考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，所有公共子序列的权重和的最大值（需满足非负条件）。但直接这样定义无法处理“非负”约束，因此扩展状态： dp[i][j][k] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符，且当前子序列权重和恰好为 k 时，是否存在这样的公共子序列（布尔值）。 然而 k 的范围可能很大（权重和可能为负或正），需优化。 状态优化 由于权重和需非负，可定义 dp[i][j] 为最大非负权重和。若没有合法子序列，记为 -∞ 。但转移时需确保每一步的中间状态权重和非负，这可能导致错误（因为中间状态可能暂时为负，但最终非负）。 更稳妥的方法： 令 dp[i][j] 为考虑前 i 和 j 个字符时，所有公共子序列的最大权重和（不要求非负），同时用辅助数组 valid[i][j] 记录是否存在权重和非负的子序列。 但这样无法保证转移时利用非负子序列。 最终方案 使用二维动态规划，但状态记录两个值： max_sum[i][j] ：考虑 s1[0:i] 和 s2[0:j] 时，公共子序列的最大权重和（允许为负）。 max_nonneg[i][j] ：在相同范围内，权重和非负的公共子序列的最大权重和（若不存在则为 -∞ ）。 转移时分类讨论： 不选当前字符：继承 (i-1, j) 或 (i, j-1) 的状态。 若 s1[i-1] == s2[j-1] ，选择当前字符：从 (i-1, j-1) 的状态加上当前字符权重 w[ch] ，更新 max_sum 和 max_nonneg 。 具体步骤： a. 初始化： max_sum[0][j] = max_sum[i][0] = 0 （空子序列权重为0）， max_nonneg[0][j] = max_nonneg[i][0] = 0 。 b. 转移方程： max_sum[i][j] = max(max_sum[i-1][j], max_sum[i][j-1], max_sum[i-1][j-1] + w[s1[i-1]]) （若字符匹配）。 对于 max_nonneg[i][j] ： 不选当前字符：从 max_nonneg[i-1][j] 和 max_nonneg[i][j-1] 继承。 若字符匹配，且从 (i-1, j-1) 转移： 若 max_nonneg[i-1][j-1] 非负，新和 = max_nonneg[i-1][j-1] + w[ch] ，若新和 ≥ 0，则更新。 若 max_sum[i-1][j-1] + w[ch] ≥ 0，也可能更新（即使 max_nonneg[i-1][j-1] 为负，但新和可能非负）。 c. 最终答案： max(0, max_nonneg[m][n]) （若为 -∞ 则输出0，表示空子序列）。 举例说明 设 s1 = "ab", s2 = "acb" ，权重： a:1, b:-2, c:3 。 初始化： max_nonneg[0][*] = 0 。 i=1, j=1 （字符 a 匹配）： max_nonneg[1][1] = max(0, 0+1) = 1 。 i=1, j=2 （不匹配）：继承左侧和上方，得 max_nonneg=1 。 i=2, j=3 （字符 b 匹配）：从 (1,2) 转移，新和 1 + (-2) = -1 （无效）；从 max_sum[1][2] 可能为1，新和-1无效。但存在子序列 "a" 权重1，故最终答案1。 此方法确保在权重和非负条件下找到最优解。