线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负）

题目描述
给定两个字符串 s1 和 s2，以及一个字符权重表 weight（每个字符对应一个整数权重，权重可为负数）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列的权重和（即子序列中每个字符权重的总和）非负，且长度尽可能长。输出这个最长公共子序列的长度。若不存在满足条件的公共子序列，则返回 0。

示例
输入：
s1 = "ab", s2 = "ba", weight = {'a': 2, 'b': -1}
输出：
2
解释：公共子序列 "a" 的权重和为 2（非负），"b" 的权重和为 -1（无效），"ab" 或 "ba" 的权重和为 2 + (-1) = 1（非负），且长度为 2，是最长满足条件的。

解题过程

1. 问题分析

   • 在经典 LCS 问题基础上，增加了字符权重和权重和非负的限制。
   • 难点：权重可为负，需确保子序列权重和 ≥ 0，同时最大化子序列长度。
   • 思路：动态规划状态需记录当前权重和，但权重和可能为负且范围未知，直接作为状态维度可能爆炸。

2. 状态设计

   • 定义 dp[i][j][w]：考虑 s1 的前 i 个字符和 s2 的前 j 个字符，能否形成权重和恰好为 w 的公共子序列，并记录该子序列的最大长度。
   • 但 w 的范围可能很大（负权重导致和可负）。优化：将权重和偏移到一个非负区间。
   • 设权重最小和为 min_sum（全选负权字符），最大和为 max_sum（全选正权字符）。通过偏移量 offset = -min_sum 将权重和映射到非负索引。

3. 状态转移

   • 初始化：dp[0][0][0 + offset] = 0，表示空子序列权重和为 0，长度为 0。
   • 对于每个 (i, j)：
     • 不选 s1[i-1] 或 s2[j-1]：继承 dp[i-1][j][w] 和 dp[i][j-1][w]。
     • 若 s1[i-1] == s2[j-1]，且当前字符权重为 wt：

       对于所有可能的 w，若 dp[i-1][j-1][w] 有效，则更新 dp[i][j][w + wt] = max(dp[i][j][w + wt], dp[i-1][j-1][w] + 1)  
       

   • 注意：权重和 w + wt 需在合法范围内（偏移后索引非负且不超过 max_sum + offset）。

4. 复杂度优化

   • 直接三维 DP 可能超时（O(n² * (max_sum - min_sum))）。
   • 优化：使用二维 DP，但状态为 (i, j) -> 映射表，记录当前所有可能的权重和及对应最大长度。通过哈希表或数组压缩状态。
   • 具体：用 dp[i][j] 存储一个字典，键为权重和（偏移后），值为最大长度。转移时仅遍历可能的权重和。

5. 最终答案

   • 遍历所有 (i, j) 对应的状态，找到权重和 w ≥ 0（即原始权重和 ≥ 0）的最大长度。
   • 若没有满足条件的状态，返回 0。

关键点

• 通过权重和偏移处理负权问题。
• 使用字典压缩状态，避免无效计算。
• 确保最终权重和非负，且长度最大化。