线性动态规划：两个字符串的最小ASCII删除和
字数 1847 2025-10-28 08:36:45

线性动态规划：两个字符串的最小ASCII删除和

题目描述
给定两个字符串 s1 和 s2，你需要通过删除一些字符（可以是零个）使两个字符串相等。每删除一个字符，你需要付出该字符的 ASCII 值作为代价。你的目标是找到使两个字符串相等所需删除的最小 ASCII 总和。例如，若 s1 = "sea"，s2 = "eat"，删除 's'（ASCII 115）和 't'（ASCII 116）后，两个字符串都变为 "ea"，总代价为 115 + 116 = 231。

解题过程

步骤 1：问题转化
本题实质是寻找两个字符串的“最长公共子序列（LCS）”，但目标不是求 LCS 的长度，而是求 LCS 的 ASCII 值之和最大。因为删除的字符 ASCII 总和最小，等价于保留的公共子序列的 ASCII 总和最大。
设 s1 和 s2 所有字符的 ASCII 总和为 total_sum，保留的 LCS 的 ASCII 总和为 lcs_ascii_sum，则最小删除代价为：
total_sum - 2 * lcs_ascii_sum（因为保留的公共部分在两个字符串中都存在，需从总和中减去两次）。

步骤 2：定义状态
定义 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0..i-1]）和 s2 的前 j 个字符（即 s2[0..j-1]）的 LCS 的 ASCII 值之和的最大值。

  • i 的取值范围是 [0, len(s1)]，j 的取值范围是 [0, len(s2)]。
  • 当 i = 0 或 j = 0 时，表示一个字符串为空，此时公共子序列为空，ASCII 和为 0。

步骤 3：状态转移方程

  • 若 s1[i-1] == s2[j-1]：当前字符可加入公共子序列，贡献 ASCII 值 s1[i-1]。
    dp[i][j] = dp[i-1][j-1] + ord(s1[i-1])
  • 若 s1[i-1] != s2[j-1]：当前字符不能同时保留，需选择跳过 s1[i-1] 或跳过 s2[j-1] 的较大值。
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

步骤 4：初始化

  • dp[0][j] = 0（s1 为空时，公共子序列 ASCII 和为 0）
  • dp[i][0] = 0（s2 为空时，公共子序列 ASCII 和为 0）

步骤 5：计算顺序
按 i 从 1 到 len(s1)，j 从 1 到 len(s2) 的顺序填充 dp 表。

步骤 6：获取结果
计算 s1 和 s2 的总 ASCII 和：
total_ascii = sum(ord(c) for c in s1) + sum(ord(c) for c in s2)
最大公共子序列 ASCII 和为 dp[len(s1)][len(s2)]。
最小删除代价为：total_ascii - 2 * dp[len(s1)][len(s2)]。

举例说明
以 s1 = "sea"，s2 = "eat" 为例：

  • 总 ASCII 和：'s'=115, 'e'=101, 'a'=97 → 115+101+97=313；'e'=101, 'a'=97, 't'=116 → 101+97+116=314；总和为 313+314=627。
  • 构建 dp 表（尺寸 4×4）：
i\j 0 1 (e) 2 (a) 3 (t)
0 0 0 0 0
1(s) 0 0 0 0
2(e) 0 101 101 101
3(a) 0 101 198 198
  • 最大公共 ASCII 和：dp[3][3] = 198（对应公共子序列 "ea"，ASCII 和为 101+97=198）。
  • 最小删除代价：627 - 2*198 = 231，与题目示例一致。

通过以上步骤，你可逐步理解如何将问题转化为 LCS 的 ASCII 和最大化，并利用动态规划求解。

线性动态规划：两个字符串的最小ASCII删除和 题目描述 给定两个字符串 s1 和 s2 ，你需要通过删除一些字符（可以是零个）使两个字符串相等。每删除一个字符，你需要付出该字符的 ASCII 值作为代价。你的目标是找到使两个字符串相等所需删除的最小 ASCII 总和。例如，若 s1 = "sea" ， s2 = "eat" ，删除 's' （ASCII 115）和 't' （ASCII 116）后，两个字符串都变为 "ea" ，总代价为 115 + 116 = 231。 解题过程 步骤 1：问题转化 本题实质是寻找两个字符串的“最长公共子序列（LCS）”，但目标不是求 LCS 的长度，而是求 LCS 的 ASCII 值之和最大。因为删除的字符 ASCII 总和最小，等价于保留的公共子序列的 ASCII 总和最大。 设 s1 和 s2 所有字符的 ASCII 总和为 total_sum ，保留的 LCS 的 ASCII 总和为 lcs_ascii_sum ，则最小删除代价为： total_sum - 2 * lcs_ascii_sum （因为保留的公共部分在两个字符串中都存在，需从总和中减去两次）。 步骤 2：定义状态 定义 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0..i-1] ）和 s2 的前 j 个字符（即 s2[0..j-1] ）的 LCS 的 ASCII 值之和的最大值。 i 的取值范围是 [0, len(s1)] ， j 的取值范围是 [0, len(s2)] 。 当 i = 0 或 j = 0 时，表示一个字符串为空，此时公共子序列为空，ASCII 和为 0。 步骤 3：状态转移方程 若 s1[i-1] == s2[j-1] ：当前字符可加入公共子序列，贡献 ASCII 值 s1[i-1] 。 dp[i][j] = dp[i-1][j-1] + ord(s1[i-1]) 若 s1[i-1] != s2[j-1] ：当前字符不能同时保留，需选择跳过 s1[i-1] 或跳过 s2[j-1] 的较大值。 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 步骤 4：初始化 dp[0][j] = 0 （ s1 为空时，公共子序列 ASCII 和为 0） dp[i][0] = 0 （ s2 为空时，公共子序列 ASCII 和为 0） 步骤 5：计算顺序 按 i 从 1 到 len(s1) ， j 从 1 到 len(s2) 的顺序填充 dp 表。 步骤 6：获取结果 计算 s1 和 s2 的总 ASCII 和： total_ascii = sum(ord(c) for c in s1) + sum(ord(c) for c in s2) 最大公共子序列 ASCII 和为 dp[len(s1)][len(s2)] 。 最小删除代价为： total_ascii - 2 * dp[len(s1)][len(s2)] 。 举例说明 以 s1 = "sea" ， s2 = "eat" 为例： 总 ASCII 和： 's'=115, 'e'=101, 'a'=97 → 115+101+97=313； 'e'=101, 'a'=97, 't'=116 → 101+97+116=314；总和为 313+314=627。 构建 dp 表（尺寸 4×4）： | i\j | 0 | 1 (e) | 2 (a) | 3 (t) | |-----|----|------|------|------| | 0 | 0 | 0 | 0 | 0 | | 1(s)| 0 | 0 | 0 | 0 | | 2(e)| 0 | 101 | 101 | 101 | | 3(a)| 0 | 101 | 198 | 198 | 最大公共 ASCII 和： dp[3][3] = 198 （对应公共子序列 "ea" ，ASCII 和为 101+97=198）。 最小删除代价： 627 - 2*198 = 231 ，与题目示例一致。 通过以上步骤，你可逐步理解如何将问题转化为 LCS 的 ASCII 和最大化，并利用动态规划求解。