线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重）
字数 2146 2025-11-03 12:22:39

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

题目描述
给定两个字符串 s1 和 s2，长度分别为 m 和 n。每个字符 c 有一个权重 w(c)（可能为正、负或零）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列中所有字符的权重之和最大。输出这个最大权重和。

示例
输入：
s1 = "ABC", s2 = "ACB"
权重：w('A') = 1, w('B') = -2, w('C') = 3
输出：4
解释：公共子序列 "AC" 的权重和为 1 + 3 = 4；另一个子序列 "AB" 的权重和为 1 + (-2) = -1；"AC" 是最优解。

解题过程

步骤1：定义状态
设 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0..i-1]）与 s2 的前 j 个字符（即 s2[0..j-1]）的带权重最长公共子序列的最大权重和。

  • i 的取值范围：0 <= i <= m
  • j 的取值范围：0 <= j <= n

步骤2：初始化边界

  • 当 i = 0 或 j = 0 时，表示其中一个字符串为空，公共子序列为空，权重和为 0：
    dp[0][j] = 0（对任意 j）
    dp[i][0] = 0（对任意 i）

步骤3：状态转移方程
考虑 s1[i-1] 和 s2[j-1] 是否相等：

  1. 若 s1[i-1] == s2[j-1]：

    • 可以选择将当前字符加入公共子序列，此时权重和增加 w(s1[i-1])，并加上前一部分的最优解 dp[i-1][j-1]。
    • 也可以选择不加入当前字符，此时继承 dp[i-1][j] 或 dp[i][j-1] 的较大值。
    • 转移方程：
      dp[i][j] = max(dp[i-1][j-1] + w(s1[i-1]), dp[i-1][j], dp[i][j-1])

  2. 若 s1[i-1] != s2[j-1]：

    • 当前字符不能同时加入公共子序列，但可以继承 s1 少一个字符或 s2 少一个字符时的最优解：
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

注意：由于权重可能为负，必须考虑“不选当前字符”的情况（即与 dp[i-1][j] 或 dp[i][j-1] 比较），否则可能错过最优解。

步骤4：递推计算
按 i 从 1 到 m、j 从 1 到 n 的顺序填充 dp 表。
以示例 s1 = "ABC", s2 = "ACB" 为例（权重：A=1, B=-2, C=3）：

初始化：

dp[0][*] = 0, dp[*][0] = 0

计算过程：

  • i=1, j=1：s1[0]='A', s2[0]='A'，相等 → dp[1][1] = max(0+1, dp[0][1]=0, dp[1][0]=0) = 1
  • i=1, j=2：s1[0]='A', s2[1]='C'，不等 → dp[1][2] = max(dp[0][2]=0, dp[1][1]=1) = 1
  • i=1, j=3：s1[0]='A', s2[2]='B'，不等 → dp[1][3] = max(dp[0][3]=0, dp[1][2]=1) = 1
  • i=2, j=1：s1[1]='B', s2[0]='A'，不等 → dp[2][1] = max(dp[1][1]=1, dp[2][0]=0) = 1
  • i=2, j=2：s1[1]='B', s2[1]='C'，不等 → dp[2][2] = max(dp[1][2]=1, dp[2][1]=1) = 1
  • i=2, j=3：s1[1]='B', s2[2]='B'，相等 → dp[2][3] = max(dp[1][2]=1 + (-2), dp[1][3]=1, dp[2][2]=1) = max(-1, 1, 1) = 1
  • i=3, j=1：s1[2]='C', s2[0]='A'，不等 → dp[3][1] = max(dp[2][1]=1, dp[3][0]=0) = 1
  • i=3, j=2：s1[2]='C', s2[1]='C'，相等 → dp[3][2] = max(dp[2][1]=1 + 3, dp[2][2]=1, dp[3][1]=1) = max(4, 1, 1) = 4
  • i=3, j=3：s1[2]='C', s2[2]='B'，不等 → dp[3][3] = max(dp[2][3]=1, dp[3][2]=4) = 4

最终结果：dp[3][3] = 4。

步骤5：复杂度分析

  • 时间复杂度：O(m·n)，需要填充一个 m×n 的二维表。
  • 空间复杂度：O(m·n)，可优化至 O(min(m, n))（只保留当前行和上一行）。

关键点

  • 允许负权重时，必须始终通过 max 比较确保不遗漏更优解。
  • 若要求输出具体子序列，需额外记录路径（通过 pre[i][j] 标记状态来源）。
线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重） 题目描述 给定两个字符串 s1 和 s2 ，长度分别为 m 和 n 。每个字符 c 有一个权重 w(c) （可能为正、负或零）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列中所有字符的权重之和最大。输出这个最大权重和。 示例 输入： s1 = "ABC", s2 = "ACB" 权重：w('A') = 1, w('B') = -2, w('C') = 3 输出：4 解释：公共子序列 "AC" 的权重和为 1 + 3 = 4；另一个子序列 "AB" 的权重和为 1 + (-2) = -1；"AC" 是最优解。 解题过程 步骤1：定义状态 设 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0..i-1] ）与 s2 的前 j 个字符（即 s2[0..j-1] ）的 带权重最长公共子序列 的最大权重和。 i 的取值范围： 0 <= i <= m j 的取值范围： 0 <= j <= n 步骤2：初始化边界 当 i = 0 或 j = 0 时，表示其中一个字符串为空，公共子序列为空，权重和为 0： dp[0][j] = 0 （对任意 j ） dp[i][0] = 0 （对任意 i ） 步骤3：状态转移方程 考虑 s1[i-1] 和 s2[j-1] 是否相等： 若 s1[i-1] == s2[j-1] ： 可以选择将当前字符加入公共子序列，此时权重和增加 w(s1[i-1]) ，并加上前一部分的最优解 dp[i-1][j-1] 。 也可以选择不加入当前字符，此时继承 dp[i-1][j] 或 dp[i][j-1] 的较大值。 转移方程： dp[i][j] = max(dp[i-1][j-1] + w(s1[i-1]), dp[i-1][j], dp[i][j-1]) 若 s1[i-1] != s2[j-1] ： 当前字符不能同时加入公共子序列，但可以继承 s1 少一个字符或 s2 少一个字符时的最优解： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 注意 ：由于权重可能为负，必须考虑“不选当前字符”的情况（即与 dp[i-1][j] 或 dp[i][j-1] 比较），否则可能错过最优解。 步骤4：递推计算 按 i 从 1 到 m 、 j 从 1 到 n 的顺序填充 dp 表。 以示例 s1 = "ABC" , s2 = "ACB" 为例（权重：A=1, B=-2, C=3）： 初始化： 计算过程： i=1, j=1 ：s1[ 0]='A', s2[ 0]='A'，相等 → dp[1][1] = max(0+1, dp[0][1]=0, dp[1][0]=0) = 1 i=1, j=2 ：s1[ 0]='A', s2[ 1]='C'，不等 → dp[1][2] = max(dp[0][2]=0, dp[1][1]=1) = 1 i=1, j=3 ：s1[ 0]='A', s2[ 2]='B'，不等 → dp[1][3] = max(dp[0][3]=0, dp[1][2]=1) = 1 i=2, j=1 ：s1[ 1]='B', s2[ 0]='A'，不等 → dp[2][1] = max(dp[1][1]=1, dp[2][0]=0) = 1 i=2, j=2 ：s1[ 1]='B', s2[ 1]='C'，不等 → dp[2][2] = max(dp[1][2]=1, dp[2][1]=1) = 1 i=2, j=3 ：s1[ 1]='B', s2[ 2]='B'，相等 → dp[2][3] = max(dp[1][2]=1 + (-2), dp[1][3]=1, dp[2][2]=1) = max(-1, 1, 1) = 1 i=3, j=1 ：s1[ 2]='C', s2[ 0]='A'，不等 → dp[3][1] = max(dp[2][1]=1, dp[3][0]=0) = 1 i=3, j=2 ：s1[ 2]='C', s2[ 1]='C'，相等 → dp[3][2] = max(dp[2][1]=1 + 3, dp[2][2]=1, dp[3][1]=1) = max(4, 1, 1) = 4 i=3, j=3 ：s1[ 2]='C', s2[ 2]='B'，不等 → dp[3][3] = max(dp[2][3]=1, dp[3][2]=4) = 4 最终结果： dp[3][3] = 4 。 步骤5：复杂度分析 时间复杂度：O(m·n)，需要填充一个 m×n 的二维表。 空间复杂度：O(m·n)，可优化至 O(min(m, n))（只保留当前行和上一行）。 关键点 允许负权重时，必须始终通过 max 比较确保不遗漏更优解。 若要求输出具体子序列，需额外记录路径（通过 pre[i][j] 标记状态来源）。