最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负）
字数 2185 2025-11-05 23:45:42

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

题目描述
给定两个字符串 s 和 t，以及一个权重函数 w(c)，为每个字符 c 分配一个整数权重（可能为负数）。要求找到 s 和 t 的一个公共子序列，使得该子序列的权重和（即子序列中每个字符权重的总和）非负，且在所有满足非负权重和的公共子序列中长度最长。输出这个最长长度。

示例
输入：
s = "ABBC", t = "ABCC"
权重函数：w(A)=1, w(B)=-1, w(C)=2
输出：3
解释：公共子序列 "ABC" 的权重和为 1 + (-1) + 2 = 2（非负），且是所有非负权公共子序列中最长的。

解题过程

步骤1：问题分析
本题是最长公共子序列（LCS）的变种，增加了字符权重和权重和非负的约束。直接应用LCS的动态规划方法无法处理权重约束，需扩展状态定义。

步骤2：状态定义
设 dp[i][j][k] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，能否得到一个公共子序列的权重和恰好为 k，且该子序列的长度。但权重和 k 的范围可能很大（由于负权重），需确定其上下界。

  • 权重和的最小可能值：若所有字符权重为负，子序列为空时权重和为0（空序列视为权重和0）。
  • 权重和的最大可能值：假设所有字符权重为正，最长子序列的权重和不超过 min(len(s), len(t)) * max_weight。
    但允许负权重后，实际范围可能很大。然而，我们只关心非负权重和（k ≥ 0），且 k 最大不超过可能的最大正权和。可设定一个足够大的上界 M（如 min(m, n) * max_w，其中 max_w 是最大正权重）。

优化：使用偏移量技巧。若权重最小值为 min_w（负值），则将权重和整体偏移 -min_w * min(m, n)，使所有可能权重和变为非负，便于数组索引。

步骤3：动态规划转移方程
定义 dp[i][j][k] 表示考虑 s[0:i] 和 t[0:j]，公共子序列权重和恰好为 k 时的最大子序列长度。若无法达到权重和 k，设为 -∞。

初始化：
dp[0][0][0] = 0（空序列），其余为 -∞。

转移方程：

  1. 不选 s[i-1] 或 t[j-1]：
    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k], dp[i][j-1][k])
  2. 若 s[i-1] == t[j-1]，且加入字符 c = s[i-1]：
    设 wt = w(c)，若 k - wt >= 0，则
    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k - wt] + 1)

最终答案：对所有 k ≥ 0，取 dp[m][n][k] 的最大值。

步骤4：复杂度优化
直接三维DP的复杂度为 O(m * n * M)，其中 M 是权重和范围，可能过大。注意：我们只关心非负 k，且 M 由实际权重范围决定。若权重绝对值不大，可接受；否则需优化。

优化思路：将状态定义为 dp[i][j] 是一个字典，键为权重和，值为最大长度。这样只存储可能出现的权重和，避免遍历整个范围。

步骤5：实现细节（使用字典优化）

  • 初始化：dp[0][0] = {0: 0}（权重和0对应长度0）。
  • 转移：
    • 继承 dp[i-1][j] 和 dp[i][j-1] 的所有状态。
    • 若 s[i-1] == t[j-1]，对 dp[i-1][j-1] 中的每个权重和 wt_sum，计算新权重和 new_wt = wt_sum + w(s[i-1])，新长度 new_len = old_len + 1。若 new_wt 已存在，取最大长度；否则添加。
  • 最终遍历 dp[m][n] 中所有 wt_sum ≥ 0 的项，找最大长度。

步骤6：示例演算
s = "ABBC", t = "ABCC", w(A)=1, w(B)=-1, w(C)=2。

初始化：dp[0][0] = {0:0}

处理 i=1, j=1:

  • 继承：dp[1][0] = {0:0}, dp[0][1] = {0:0}
  • 匹配：s[0]='A' = t[0]='A'，由 dp[0][0] 得新状态 {1:1}
  • 合并：dp[1][1] = max({0:0}, {1:1}) → {0:0, 1:1}

处理 i=1, j=2:

  • 继承：dp[1][1] 和 dp[0][2]
  • 无匹配（s[0]='A' ≠ t[1]='B'）
  • 结果：dp[1][2] = {0:0, 1:1}

继续至 i=4, j=4：
最终 dp[4][4] 包含状态，如权重和2对应长度3（子序列"ABC"）。
在所有 k≥0 中，最大长度为3。

总结
本题通过扩展LCS的状态，增加权重和维度，并利用字典优化处理权重范围，解决了带非负权重和约束的最长公共子序列问题。

最长公共子序列的变种：带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负） 题目描述 给定两个字符串 s 和 t ，以及一个权重函数 w(c) ，为每个字符 c 分配一个整数权重（可能为负数）。要求找到 s 和 t 的一个公共子序列，使得该子序列的权重和（即子序列中每个字符权重的总和）非负，且在所有满足非负权重和的公共子序列中长度最长。输出这个最长长度。 示例 输入： s = "ABBC" , t = "ABCC" 权重函数： w(A)=1, w(B)=-1, w(C)=2 输出：3 解释：公共子序列 "ABC" 的权重和为 1 + (-1) + 2 = 2 （非负），且是所有非负权公共子序列中最长的。 解题过程 步骤1：问题分析 本题是最长公共子序列（LCS）的变种，增加了字符权重和权重和非负的约束。直接应用LCS的动态规划方法无法处理权重约束，需扩展状态定义。 步骤2：状态定义 设 dp[i][j][k] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，能否得到一个公共子序列的权重和恰好为 k ，且该子序列的长度。但权重和 k 的范围可能很大（由于负权重），需确定其上下界。 权重和的最小可能值：若所有字符权重为负，子序列为空时权重和为0（空序列视为权重和0）。 权重和的最大可能值：假设所有字符权重为正，最长子序列的权重和不超过 min(len(s), len(t)) * max_weight 。 但允许负权重后，实际范围可能很大。然而，我们只关心非负权重和（ k ≥ 0 ），且 k 最大不超过可能的最大正权和。可设定一个足够大的上界 M （如 min(m, n) * max_w ，其中 max_w 是最大正权重）。 优化：使用偏移量技巧。若权重最小值为 min_w （负值），则将权重和整体偏移 -min_w * min(m, n) ，使所有可能权重和变为非负，便于数组索引。 步骤3：动态规划转移方程 定义 dp[i][j][k] 表示考虑 s[0:i] 和 t[0:j] ，公共子序列权重和恰好为 k 时的最大子序列长度。若无法达到权重和 k ，设为 -∞ 。 初始化： dp[0][0][0] = 0 （空序列），其余为 -∞ 。 转移方程： 不选 s[i-1] 或 t[j-1] ： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k], dp[i][j-1][k]) 若 s[i-1] == t[j-1] ，且加入字符 c = s[i-1] ： 设 wt = w(c) ，若 k - wt >= 0 ，则 dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k - wt] + 1) 最终答案：对所有 k ≥ 0 ，取 dp[m][n][k] 的最大值。 步骤4：复杂度优化 直接三维DP的复杂度为 O(m * n * M) ，其中 M 是权重和范围，可能过大。注意：我们只关心非负 k ，且 M 由实际权重范围决定。若权重绝对值不大，可接受；否则需优化。 优化思路：将状态定义为 dp[i][j] 是一个字典，键为权重和，值为最大长度。这样只存储可能出现的权重和，避免遍历整个范围。 步骤5：实现细节（使用字典优化） 初始化： dp[0][0] = {0: 0} （权重和0对应长度0）。 转移： 继承 dp[i-1][j] 和 dp[i][j-1] 的所有状态。 若 s[i-1] == t[j-1] ，对 dp[i-1][j-1] 中的每个权重和 wt_sum ，计算新权重和 new_wt = wt_sum + w(s[i-1]) ，新长度 new_len = old_len + 1 。若 new_wt 已存在，取最大长度；否则添加。 最终遍历 dp[m][n] 中所有 wt_sum ≥ 0 的项，找最大长度。 步骤6：示例演算 s = "ABBC" , t = "ABCC" , w(A)=1, w(B)=-1, w(C)=2 。 初始化： dp[0][0] = {0:0} 处理 i=1, j=1: 继承： dp[1][0] = {0:0} , dp[0][1] = {0:0} 匹配： s[0]='A' = t[0]='A' ，由 dp[0][0] 得新状态 {1:1} 合并： dp[1][1] = max({0:0}, {1:1}) → {0:0, 1:1} 处理 i=1, j=2: 继承： dp[1][1] 和 dp[0][2] 无匹配（s[ 0]='A' ≠ t[ 1 ]='B'） 结果： dp[1][2] = {0:0, 1:1} 继续至 i=4, j=4： 最终 dp[4][4] 包含状态，如权重和2对应长度3（子序列"ABC"）。 在所有 k≥0 中，最大长度为3。 总结 本题通过扩展LCS的状态，增加权重和维度，并利用字典优化处理权重范围，解决了带非负权重和约束的最长公共子序列问题。