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

字数 2537 2025-11-06 22:52:24

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

题目描述
给定两个字符串 s1 和 s2，长度分别为 m 和 n。每个字符 c 在字符串中出现时都有一个对应的权重 weight[c]（权重可以是负数、零或正数）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列的字符权重之和最大，且权重和必须非负。公共子序列定义为同时是 s1 和 s2 子序列的字符序列。

示例
输入：
s1 = "ab", s2 = "ba"
weight = {'a': 2, 'b': -1}
输出：最大权重和为 2（对应公共子序列 "a"，权重和 = 2；子序列 "b" 权重和为 -1，不满足非负条件；子序列 "ab" 或 "ba" 不是公共子序列）。

解题过程

步骤 1：问题分析
本题是最长公共子序列（LCS）的变种，但目标不是最大化子序列长度，而是最大化权重和，且权重和需非负。权重可为负，因此需考虑所有可能的公共子序列，并筛选出权重和非负中最大的。

步骤 2：定义状态
设 dp[i][j][k] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，能否得到权重和 k。但由于权重和可能很大（负权重导致范围广），直接存储所有 k 不现实。我们需优化状态定义。

优化思路：
定义 dp[i][j] 为考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，可得到的最大权重和（且非负）。但这样无法处理中间负权重的情况。因此，我们改用：
dp[i][j] 为考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，所有可能的权重和中的最大值（包括负值），但最终结果需从所有 dp[i][j] 中选非负的最大值。但这样会丢失信息，因为负权重和可能后续变为非负。

正确状态定义：
我们记录每个 (i, j) 下所有可能达到的权重和，但只关心那些可能最终贡献非负和的值。由于权重和范围可能大，我们使用“最大非负和”的思路，但需确保状态转移不遗漏。

步骤 3：状态转移方程
我们定义 dp[i][j] 为以 s1[i-1] 和 s2[j-1] 结尾的公共子序列的最大权重和（允许为负），但这样不全面，因为公共子序列不一定以当前字符结尾。因此，我们采用类似 LCS 的转移，但维护权重和。

标准解法：
设 dp[i][j] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，能得到的最大权重和（无论是否非负）。转移方程：

不选 s1[i-1] 或 s2[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
当 s1[i-1] == s2[j-1] 时，可选该字符：dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight[s1[i-1]])

但最终需从所有 dp[i][j] 中选非负的最大值。但这样正确吗？
问题：如果 dp[i-1][j-1] 为负，加上正权重后可能变为非负，但上述转移会继承负值，可能漏掉解。例如，s1="a", s2="a", weight{'a'}=10，初始 dp[0][0]=0，但 dp[1][1] = max(0, 0, 0+10)=10，正确。

关键点：初始状态 dp[0][0] = 0（空子序列，权重和0），其他 dp[i][j] 初始为负无穷（表示未达到）。这样，只要存在公共子序列，其和就会从0开始累加。

步骤 4：处理非负约束
我们最终答案是 max(0, max_{i,j} {dp[i][j]})，因为空子序列权重和为0（非负），所以答案至少为0。如果所有公共子序列权重和为负，则取0（空序列）。

步骤 5：算法实现

初始化 dp 矩阵，尺寸 (m+1) x (n+1)，dp[0][0] = 0，其他为 -inf。
遍历 i 从0到 m，j 从0到 n：
- 如果 i>0，更新 dp[i][j] = max(dp[i][j], dp[i-1][j])（不选 s1[i-1]）
- 如果 j>0，更新 dp[i][j] = max(dp[i][j], dp[i][j-1])（不选 s2[j-1]）
- 如果 i>0 且 j>0 且 s1[i-1] == s2[j-1]，更新 dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight[s1[i-1]])
答案 ans = max(0, max_{i,j} dp[i][j])

步骤 6：示例验证
s1="ab", s2="ba", weight{'a'=2, 'b'=-1

dp[0][0]=0
dp[1][0] = max(-inf, dp[0][0]) = 0（不选 'a'）
dp[0][1] = 0
dp[1][1]：字符 'a' != 'b'，所以 max(dp[0][1], dp[1][0]) = max(0,0)=0
dp[1][2]：s1[0]='a' 等于 s2[1]='a'，所以 max(dp[0][1]+2=2, dp[1][1]=0, dp[0][2]=0) = 2
dp[2][1]：类似，得 max(dp[1][0]+(-1)=-1, ...) = 0
dp[2][2]：'b'=='b'，max(dp[1][1]+(-1)=-1, dp[2][1]=0, dp[1][2]=2) = 2
最终 ans = max(0,2) = 2，正确。

总结
本题通过扩展 LCS 的动态规划，维护每个状态的最大权重和，最终取非负最大值。初始状态 dp[0][0]=0 确保空子序列被考虑，负权重通过累加处理，最终结果满足非负约束。

线性动态规划：最长公共子序列的变种——带字符权重的最长公共子序列（进阶版：允许负权重且要求子序列权重和非负）题目描述给定两个字符串 s1 和 s2 ，长度分别为 m 和 n 。每个字符 c 在字符串中出现时都有一个对应的权重 weight[c] （权重可以是负数、零或正数）。要求找到 s1 和 s2 的一个公共子序列，使得该子序列的字符权重之和最大，且权重和必须非负。公共子序列定义为同时是 s1 和 s2 子序列的字符序列。示例输入： s1 = "ab" , s2 = "ba" weight = {'a': 2, 'b': -1} 输出：最大权重和为 2（对应公共子序列 "a" ，权重和 = 2；子序列 "b" 权重和为 -1，不满足非负条件；子序列 "ab" 或 "ba" 不是公共子序列）。解题过程步骤 1：问题分析本题是最长公共子序列（LCS）的变种，但目标不是最大化子序列长度，而是最大化权重和，且权重和需非负。权重可为负，因此需考虑所有可能的公共子序列，并筛选出权重和非负中最大的。步骤 2：定义状态设 dp[i][j][k] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，能否得到权重和 k 。但由于权重和可能很大（负权重导致范围广），直接存储所有 k 不现实。我们需优化状态定义。优化思路：定义 dp[i][j] 为考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，可得到的最大权重和（且非负）。但这样无法处理中间负权重的情况。因此，我们改用： dp[i][j] 为考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，所有可能的权重和中的最大值（包括负值），但最终结果需从所有 dp[i][j] 中选非负的最大值。但这样会丢失信息，因为负权重和可能后续变为非负。正确状态定义：我们记录每个 (i, j) 下所有可能达到的权重和，但只关心那些可能最终贡献非负和的值。由于权重和范围可能大，我们使用“最大非负和”的思路，但需确保状态转移不遗漏。步骤 3：状态转移方程我们定义 dp[i][j] 为以 s1[i-1] 和 s2[j-1] 结尾的公共子序列的最大权重和（允许为负），但这样不全面，因为公共子序列不一定以当前字符结尾。因此，我们采用类似 LCS 的转移，但维护权重和。标准解法：设 dp[i][j] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，能得到的最大权重和（无论是否非负）。转移方程：不选 s1[i-1] 或 s2[j-1] ： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 当 s1[i-1] == s2[j-1] 时，可选该字符： dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight[s1[i-1]]) 但最终需从所有 dp[i][j] 中选非负的最大值。但这样正确吗？问题：如果 dp[i-1][j-1] 为负，加上正权重后可能变为非负，但上述转移会继承负值，可能漏掉解。例如， s1="a", s2="a", weight{'a'}=10 ，初始 dp[0][0]=0 ，但 dp[1][1] = max(0, 0, 0+10)=10 ，正确。关键点：初始状态 dp[0][0] = 0 （空子序列，权重和0），其他 dp[i][j] 初始为负无穷（表示未达到）。这样，只要存在公共子序列，其和就会从0开始累加。步骤 4：处理非负约束我们最终答案是 max(0, max_{i,j} {dp[i][j]}) ，因为空子序列权重和为0（非负），所以答案至少为0。如果所有公共子序列权重和为负，则取0（空序列）。步骤 5：算法实现初始化 dp 矩阵，尺寸 (m+1) x (n+1) ， dp[0][0] = 0 ，其他为 -inf 。遍历 i 从0到 m ， j 从0到 n ：如果 i>0 ，更新 dp[i][j] = max(dp[i][j], dp[i-1][j]) （不选 s1[i-1] ）如果 j>0 ，更新 dp[i][j] = max(dp[i][j], dp[i][j-1]) （不选 s2[j-1] ）如果 i>0 且 j>0 且 s1[i-1] == s2[j-1] ，更新 dp[i][j] = max(dp[i][j], dp[i-1][j-1] + weight[s1[i-1]]) 答案 ans = max(0, max_{i,j} dp[i][j]) 步骤 6：示例验证 s1="ab", s2="ba", weight{'a'=2, 'b'=-1 dp[0][0]=0 dp[1][0] = max(-inf, dp[0][0]) = 0 （不选 'a'） dp[0][1] = 0 dp[1][1] ：字符 'a' != 'b'，所以 max(dp[0][1], dp[1][0]) = max(0,0)=0 dp[1][2] ： s1[0]='a' 等于 s2[1]='a' ，所以 max(dp[0][1]+2=2, dp[1][1]=0, dp[0][2]=0) = 2 dp[2][1] ：类似，得 max(dp[1][0]+(-1)=-1, ...) = 0 dp[2][2] ：'b'=='b'， max(dp[1][1]+(-1)=-1, dp[2][1]=0, dp[1][2]=2) = 2 最终 ans = max(0,2) = 2 ，正确。总结本题通过扩展 LCS 的动态规划，维护每个状态的最大权重和，最终取非负最大值。初始状态 dp[0][0]=0 确保空子序列被考虑，负权重通过累加处理，最终结果满足非负约束。