线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负） 题目描述 给定两个字符串 s1 和 s2 ，每个字符都有一个权重（权重可以是正数、负数或零）。要求找到一个公共子序列，使得该子序列的字符权重之和非负，并且在所有满足条件的公共子序列中，权重之和最大。如果不存在这样的子序列，返回 0。 示例 s1 = "ab", s2 = "ba" 字符权重：a: 2, b: -1 可能的公共子序列： "a"：权重和 = 2（非负，有效） "b"：权重和 = -1（负，无效） "ab"：权重和 = 2 + (-1) = 1（非负，有效） "ba"：同"ab" 最大权重和 = max(2, 1) = 2 解题过程 定义状态 设 dp[i][j][w] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，能否得到权重和为 w 的公共子序列。由于权重和可能为负，我们需要对权重进行偏移处理（例如，将所有权重加上一个足够大的常数，使其非负）。 更优解法：使用 dp[i][j] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，最大的非负权重和。但直接这样定义无法处理中间状态可能为负的情况。 状态转移 若 s1[i-1] == s2[j-1] ： 选择匹配当前字符，则权重和增加 weight[s1[i-1]] 。 若匹配后权重和非负： dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight[s1[i-1]]) 若匹配后权重和为负，则不能选择该字符（因为要求非负）。 若不匹配： 继承之前状态： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 权重偏移处理 由于权重可能为负，直接使用二维 DP 可能丢失信息。我们可以将权重偏移到非负区间： 计算所有权重的最小可能和（全选负权字符）和最大可能和（全选正权字符）。 设偏移量 offset = -min_sum ，将权重和范围映射到 [0, max_sum - min_sum] 。 定义 dp[i][j][k] 为布尔值，表示能否达到偏移后的权重和 k。最后遍历所有 k ≥ offset，找到最大的有效 k - offset。 优化空间 使用滚动数组优化第三维（权重和维度），但需注意遍历顺序。 举例说明 s1 = "a", s2 = "a", 权重：a: -1 偏移量 offset = 1（最小和 -1，偏移后为 0） dp[ 1][ 1][ 0 ] = true（空子序列，权重和 0） 匹配字符 'a'：权重和 = -1，偏移后为 0，但要求非负，故不更新。 结果 = 0（空子序列）。 总结 本题通过权重偏移将负权重问题转化为非负问题，利用三维 DP 记录可达的权重和，最后筛选满足条件的最大值。