最长公共子序列的变种：带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价）

字数 3089 2025-11-06 12:40:14

最长公共子序列的变种：带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价）

题目描述

我们有两个字符串 text1 和 text2，长度分别为 m 和 n。我们的目标是找到它们的最长公共子序列（LCS）的长度。但是，这个经典问题有一个进阶的变种：我们允许对 text2 中的字符进行替换操作，以使其与 text1 的某个子序列匹配。然而，替换操作是有代价的。具体规则如下：

我们可以选择 text2 的一个子序列（不一定连续），并尝试将其与 text1 的某个子序列匹配。
匹配过程中，对于 text2 子序列中的每个字符，如果它与 text1 子序列中对应位置的字符相同，则没有代价。
如果字符不同，我们可以进行一次替换操作，将 text2 的这个字符替换成 text1 的对应字符，从而使其匹配。但这个替换操作有一个特定的代价 cost，这个代价可能因字符的不同而不同。我们用一个函数 cost(x, y) 表示，其中 x 是 text2 中的原字符，y 是 text1 中的目标字符。注意，x 和 y 可能来自一个有限的字符集（例如小写字母）。
我们有一个总预算 B。所有替换操作的总代价不能超过这个预算 B。
我们的目标是：在总替换代价不超过预算 B 的前提下，找到最长的公共子序列（即匹配上的字符对的数量最多）。

解题过程

这个问题是 LCS 经典问题的带权变种。我们需要在状态转移时，额外考虑替换操作的代价以及总预算的限制。

第一步：定义状态

我们使用一个三维动态规划数组 dp。

令 dp[i][j][k] 表示：考虑 text1 的前 i 个字符和 text2 的前 j 个字符，并且在总替换代价恰好为 k 的情况下，所能形成的最长公共子序列的长度。
i 的范围是 0 到 m (text1的长度)。
j 的范围是 0 到 n (text2的长度)。
k 的范围是 0 到 B (总预算)。

第二步：初始化状态

初始化是动态规划的基础，它代表了考虑空字符串的情况。

dp[0][j][k] = 0：当 text1 是空字符串时，无论 text2 是什么，或者有多少预算，最长公共子序列的长度都是 0。
dp[i][0][k] = 0：当 text2 是空字符串时，同理，最长公共子序列的长度也是 0。
对于所有 k > 0，dp[0][0][k] = 0。dp[0][0][0] = 0 也是成立的，因为两个空字符串的 LCS 是 0。

第三步：状态转移方程

现在，我们考虑如何从已知状态推导出 dp[i][j][k]。对于当前位置 (i, j)，我们有两个选择：

不将 text1[i-1] 和 text2[j-1] 纳入公共子序列。
在这种情况下，最长公共子序列的长度由 text1 的前 i-1 个字符和 text2 的前 j 个字符决定，或者由 text1 的前 i 个字符和 text2 的前 j-1 个字符决定，并且预算 k 保持不变。
- candidate1 = dp[i-1][j][k]
- candidate2 = dp[i][j-1][k]
  我们取两者的最大值。
将 text1[i-1] 和 text2[j-1] 纳入公共子序列。
这只有在两个字符能够匹配的情况下才可能。这里有两种子情况：
- 字符相同 (text1[i-1] == text2[j-1])： 不需要替换，代价为 0。那么，当前长度就等于 text1 的前 i-1 个字符和 text2 的前 j-1 个字符在预算 k 下的最长公共子序列长度加 1。
  - candidate3 = dp[i-1][j-1][k] + 1
- 字符不同 (text1[i-1] != text2[j-1])： 我们可以选择进行替换。替换的代价是 c = cost(text2[j-1], text1[i-1])。这个操作只有在当前预算 k 大于等于这个代价 c 时才是可行的。如果可行，那么当前长度就等于 text1 的前 i-1 个字符和 text2 的前 j-1 个字符在预算 k - c 下的最长公共子序列长度加 1。
  - 如果 k >= c，则 candidate4 = dp[i-1][j-1][k - c] + 1
  - 否则，candidate4 不可行，我们将其视为一个极小值（例如 -1 或 -infinity），表示无法实现。

综合以上所有情况，dp[i][j][k] 的值应该是所有可行候选值中的最大值：
dp[i][j][k] = max(candidate1, candidate2, candidate3, candidate4)

注意： 如果 candidate3 或 candidate4 不可行（例如，i-1 或 j-1 为负数，或者预算不足），则在取最大值时应忽略它们。

第四步：确定最终答案

我们的目标是在总替换代价不超过预算 B 的前提下，找到最长的公共子序列。注意，我们的状态定义是代价恰好为 k。因此，最终答案并不是简单的 dp[m][n][B]。

我们需要检查所有可能的 k，其中 0 <= k <= B。因为只要总代价不超过 B 都是可行的。所以，最终答案是：
answer = max{ dp[m][n][k] for k in range(0, B+1) }

第五步：复杂度分析

时间复杂度： 状态总数为 O(m * n * B)。每个状态的计算是常数时间（比较几个候选值）。因此，总时间复杂度为 O(m * n * B)。
空间复杂度： 如果直接使用三维数组，空间复杂度也是 O(m * n * B)。可以通过滚动数组优化（只保留上一行或上一层的状态）将空间复杂度优化到 O(n * B)。

举例说明

假设 text1 = "abc", text2 = "acd", 预算 B = 2。
字符集为 {a, b, c, d}，代价函数简单定义为：如果字符不同，替换代价恒为 1，即 cost(x, y) = 1 (if x != y)。

我们构建 dp 表（i 从 0 到 3，j 从 0 到 3，k 从 0 到 2）。过程略，但核心思路如下：

在 i=2, j=2 (考虑 "ab" 和 "ac") 时，字符 'b' 和 'c' 不同。我们可以选择不匹配，或者花费代价 1 进行替换。如果替换，dp[2][2][1] 可能由 dp[1][1][0] + 1 得到（因为匹配了 'a'，然后替换 'c' 为 'b'）。
最终，在 dp[3][3][k] 中寻找最大值。一种可能的公共子序列是 "ac"（不替换，代价 0，长度 2）。另一种是 "abc"（将 text2 的 'd' 替换为 'c'，代价 1，总长度 3）。显然，后者更长。
所以最终答案应该是 3（在 k=1 时取得）。

这个例子展示了如何在预算限制下，通过替换操作获得比经典 LCS（"ac"，长度为 2）更长的公共子序列。

最长公共子序列的变种：带字符替换限制的最长公共子序列（进阶版：替换操作有不同代价）题目描述我们有两个字符串 text1 和 text2 ，长度分别为 m 和 n 。我们的目标是找到它们的最长公共子序列（LCS）的长度。但是，这个经典问题有一个进阶的变种：我们允许对 text2 中的字符进行替换操作，以使其与 text1 的某个子序列匹配。然而，替换操作是有代价的。具体规则如下：我们可以选择 text2 的一个子序列（不一定连续），并尝试将其与 text1 的某个子序列匹配。匹配过程中，对于 text2 子序列中的每个字符，如果它与 text1 子序列中对应位置的字符相同，则没有代价。如果字符不同，我们可以进行一次替换操作，将 text2 的这个字符替换成 text1 的对应字符，从而使其匹配。但这个替换操作有一个特定的代价 cost ，这个代价可能因字符的不同而不同。我们用一个函数 cost(x, y) 表示，其中 x 是 text2 中的原字符， y 是 text1 中的目标字符。注意， x 和 y 可能来自一个有限的字符集（例如小写字母）。我们有一个总预算 B 。所有替换操作的总代价不能超过这个预算 B 。我们的目标是：在总替换代价不超过预算 B 的前提下，找到最长的公共子序列（即匹配上的字符对的数量最多）。解题过程这个问题是 LCS 经典问题的带权变种。我们需要在状态转移时，额外考虑替换操作的代价以及总预算的限制。第一步：定义状态我们使用一个三维动态规划数组 dp 。令 dp[i][j][k] 表示：考虑 text1 的前 i 个字符和 text2 的前 j 个字符，并且在总替换代价恰好为 k 的情况下，所能形成的最长公共子序列的长度。 i 的范围是 0 到 m (text1的长度)。 j 的范围是 0 到 n (text2的长度)。 k 的范围是 0 到 B (总预算)。第二步：初始化状态初始化是动态规划的基础，它代表了考虑空字符串的情况。 dp[0][j][k] = 0 ：当 text1 是空字符串时，无论 text2 是什么，或者有多少预算，最长公共子序列的长度都是 0。 dp[i][0][k] = 0 ：当 text2 是空字符串时，同理，最长公共子序列的长度也是 0。对于所有 k > 0 ， dp[0][0][k] = 0 。 dp[0][0][0] = 0 也是成立的，因为两个空字符串的 LCS 是 0。第三步：状态转移方程现在，我们考虑如何从已知状态推导出 dp[i][j][k] 。对于当前位置 (i, j) ，我们有两个选择：不将 text1[i-1] 和 text2[j-1] 纳入公共子序列。在这种情况下，最长公共子序列的长度由 text1 的前 i-1 个字符和 text2 的前 j 个字符决定，或者由 text1 的前 i 个字符和 text2 的前 j-1 个字符决定，并且预算 k 保持不变。 candidate1 = dp[i-1][j][k] candidate2 = dp[i][j-1][k] 我们取两者的最大值。将 text1[i-1] 和 text2[j-1] 纳入公共子序列。这只有在两个字符能够匹配的情况下才可能。这里有两种子情况：字符相同 ( text1[i-1] == text2[j-1] )：不需要替换，代价为 0。那么，当前长度就等于 text1 的前 i-1 个字符和 text2 的前 j-1 个字符在预算 k 下的最长公共子序列长度加 1。 candidate3 = dp[i-1][j-1][k] + 1 字符不同 ( text1[i-1] != text2[j-1] )：我们可以选择进行替换。替换的代价是 c = cost(text2[j-1], text1[i-1]) 。这个操作只有在当前预算 k 大于等于这个代价 c 时才是可行的。如果可行，那么当前长度就等于 text1 的前 i-1 个字符和 text2 的前 j-1 个字符在预算 k - c 下的最长公共子序列长度加 1。如果 k >= c ，则 candidate4 = dp[i-1][j-1][k - c] + 1 否则， candidate4 不可行，我们将其视为一个极小值（例如 -1 或 -infinity ），表示无法实现。综合以上所有情况， dp[i][j][k] 的值应该是所有可行候选值中的最大值： dp[i][j][k] = max(candidate1, candidate2, candidate3, candidate4) 注意：如果 candidate3 或 candidate4 不可行（例如， i-1 或 j-1 为负数，或者预算不足），则在取最大值时应忽略它们。第四步：确定最终答案我们的目标是在总替换代价不超过预算 B 的前提下，找到最长的公共子序列。注意，我们的状态定义是代价恰好为 k 。因此，最终答案并不是简单的 dp[m][n][B] 。我们需要检查所有可能的 k ，其中 0 <= k <= B 。因为只要总代价不超过 B 都是可行的。所以，最终答案是： answer = max{ dp[m][n][k] for k in range(0, B+1) } 第五步：复杂度分析时间复杂度：状态总数为 O(m * n * B) 。每个状态的计算是常数时间（比较几个候选值）。因此，总时间复杂度为 O(m * n * B) 。空间复杂度：如果直接使用三维数组，空间复杂度也是 O(m * n * B) 。可以通过滚动数组优化（只保留上一行或上一层的状态）将空间复杂度优化到 O(n * B) 。举例说明假设 text1 = "abc" , text2 = "acd" , 预算 B = 2 。字符集为 {a, b, c, d} ，代价函数简单定义为：如果字符不同，替换代价恒为 1，即 cost(x, y) = 1 (if x != y) 。我们构建 dp 表（ i 从 0 到 3， j 从 0 到 3， k 从 0 到 2）。过程略，但核心思路如下：在 i=2, j=2 (考虑 "ab" 和 "ac") 时，字符 'b' 和 'c' 不同。我们可以选择不匹配，或者花费代价 1 进行替换。如果替换， dp[2][2][1] 可能由 dp[1][1][0] + 1 得到（因为匹配了 'a'，然后替换 'c' 为 'b'）。最终，在 dp[3][3][k] 中寻找最大值。一种可能的公共子序列是 "ac"（不替换，代价 0，长度 2）。另一种是 "abc"（将 text2 的 'd' 替换为 'c'，代价 1，总长度 3）。显然，后者更长。所以最终答案应该是 3（在 k=1 时取得）。这个例子展示了如何在预算限制下，通过替换操作获得比经典 LCS（"ac"，长度为 2）更长的公共子序列。