线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负，同时限制某些字符必须连续出现）

题目描述：
给定两个字符串 s 和 t，每个字符有一个权重（可能为负数），要求找到一个公共子序列，使得：

1. 子序列的权重和非负（即 ≥0）；
2. 子序列中必须连续出现某个给定的短串 pattern（即 pattern 是子序列的连续部分）；
3. 目标是最大化子序列的权重和。

例如：
s = "aabdc", t = "acbd", 权重：a:2, b:-1, c:1, d:-3, pattern = "abc"。
需找包含连续子串 "abc" 的公共子序列，且权重和非负。若 "abc" 在子序列中连续出现（权重和 2 + (-1) + 1 = 2 ≥ 0），则合法。

解题步骤（循序渐进）

步骤 1：问题拆解与状态定义

本问题是 LCS 的加强版，需同时处理：

• 字符权重（允许负值，但要求和 ≥0）；
• 连续模式约束（pattern 必须作为连续子串出现）；
• 权重非负。

关键思路：
将问题分解为两个部分：

1. 在 s 和 t 中匹配 pattern，记录所有匹配位置（即 pattern 在 s 和 t 中作为子序列的起始和结束索引）。
2. 对于每一对匹配位置，计算其前后缀的最大权重和，并确保整体权重非负。

定义状态：

• dp[i][j]：表示 s[0..i-1] 和 t[0..j-1] 的普通加权 LCS 的最大权重和（允许负值，但不处理 pattern 约束）。
• 但本题需记录 pattern 的匹配情况，因此增加状态维度：
  • pref[i][j]：在 s[0..i-1] 和 t[0..j-1] 中，以 pattern 的最后一个字符结尾的公共子序列的最大权重和（若未匹配完 pattern，则为 -inf）。
  • suff[i][j]：在 s[i-1..] 和 t[j-1..] 中，以 pattern 的第一个字符开头的公共子序列的最大权重和。

步骤 2：预处理模式匹配

设 pattern 长度为 m。
我们需要找到所有在 s 和 t 中作为子序列匹配的 pattern 的起始和结束位置。

• 用动态规划预处理 match_s[k][i]：在 s 中，使得 pattern[0..k-1] 是 s[0..i-1] 子序列的最早起始位置（若无则为 -1）。
• 类似定义 match_t[k][j] 用于 t。

转移方程（以 match_s 为例）：

初始化：match_s[0][i] = i（空模式匹配任何位置）
对于 k=1..m, i=1..n：
  若 s[i-1] == pattern[k-1]：
      match_s[k][i] = match_s[k-1][i-1]   # 匹配当前字符，起始位置继承自上一段
  否则：
      match_s[k][i] = match_s[k][i-1]     # 不匹配，继承前一个位置

步骤 3：计算前后缀 DP

前缀 DP pref[i][j]：
定义：在 s[0..i-1] 和 t[0..j-1] 中，匹配 pattern[0..k-1] 的最大权重和（k 从 0 到 m）。

• 当 k=0（空模式）：pref0[i][j] = 0。
• 转移：

  若 s[i-1] == t[j-1] == pattern[k-1]：
      pref[k][i][j] = max(pref[k][i-1][j], pref[k][i][j-1], 
                          pref[k-1][i-1][j-1] + weight(pattern[k-1]))
  否则：
      pref[k][i][j] = max(pref[k][i-1][j], pref[k][i][j-1])
  

  注意：当 k=m 时，pref[m][i][j] 即为以 pattern 完整结尾的最大权重和。

后缀 DP suff[i][j]：
类似，但从后往前计算（反转字符串和模式）。

步骤 4：合并结果并保证权重非负

对于每一对 (i, j)，若 pattern 在 s 中从 p1 到 i 匹配，在 t 中从 p2 到 j 匹配（通过 match_s 和 match_t 检查），则：

• 整体权重和 = pref[m][i][j] + suff[0][i+1][j+1]（即模式段权重 + 模式后段的最大权重）。
• 需满足该和 ≥0。

最终答案：
遍历所有 (i, j)，计算满足条件的最大权重和。若均负，返回 0（空子序列，权重为 0）。

举例说明（简化版）

设 s = "aabc", t = "acab", pattern = "ab"，权重：a:1, b:-1, c:2。

1. 匹配 pattern：

   • 在 s 中，"ab" 匹配于索引 (0,1) 和 (1,2)。
   • 在 t 中，"ab" 匹配于索引 (2,3)。

2. 计算权重：

   • 对于匹配 (i=2, j=3)：pattern 权重 = 1 + (-1) = 0。
   • 前后缀：前缀为空（权重0），后缀为 "c"（权重2）。
   • 总权重 = 0 + 2 = 2 ≥ 0，合法。

3. 最大和：比较所有匹配，取最大权重。

总结

本题通过多维 DP 状态 结合前后缀分解，将复杂约束转化为可处理的子问题。关键点是：

• 用 pref 和 suff 分别处理模式之前/后的段；
• 利用预处理快速定位模式匹配位置；
• 最终合并时检查权重非负。

通过以上步骤，即使问题约束复杂，也能系统化解决。