最长公共子序列的变种：两个字符串的最小ASCII删除和
字数 2292 2025-10-28 00:29:09

最长公共子序列的变种：两个字符串的最小ASCII删除和

题目描述
给定两个字符串 s1 和 s2，要求通过删除一些字符（可以删除任意字符串中的任意字符），使得两个字符串相等。每删除一个字符，就需要付出该字符的ASCII码值的代价。要求计算使两个字符串相等所需删除的最小ASCII码总和。

例如：
输入：s1 = "sea", s2 = "eat"
输出：231
解释：

  • 删除 's' (ASCII 115) 来自 "sea" 得到 "ea"
  • 删除 't' (ASCII 116) 来自 "eat" 得到 "ea"
    使两个字符串相等的最小删除ASCII和为 115 + 116 = 231

解题思路
这个问题是最长公共子序列（LCS）的变种。在LCS中，我们寻找最长的公共子序列；而在这里，我们需要最小化删除的ASCII总和。实际上，最大化保留的公共子序列的ASCII总和，等价于最小化删除的ASCII总和（因为两个字符串的总ASCII和是固定的）。

步骤1：定义状态
定义 dp[i][j] 表示字符串 s1 的前 i 个字符（即 s1[0..i-1]）和字符串 s2 的前 j 个字符（即 s2[0..j-1]）的最小ASCII删除和。

步骤2：状态转移方程
考虑两种情况：

  1. 如果 s1[i-1] == s2[j-1]，那么当前字符匹配，不需要删除，所以 dp[i][j] = dp[i-1][j-1]。
  2. 如果 s1[i-1] != s2[j-1]，那么我们可以选择删除 s1[i-1] 或删除 s2[j-1]，取两者中较小的代价：
    • 删除 s1[i-1]：代价为 s1[i-1] 的ASCII值 + dp[i-1][j]
    • 删除 s2[j-1]：代价为 s2[j-1] 的ASCII值 + dp[i][j-1]
      所以 dp[i][j] = min(ascii(s1[i-1]) + dp[i-1][j], ascii(s2[j-1]) + dp[i][j-1])

步骤3：初始化

  • 当 i=0 时，s1 为空，需要删除 s2 的所有前 j 个字符，所以 dp[0][j] = sum(ascii(s2[0..j-1]))
  • 当 j=0 时，s2 为空，需要删除 s1 的所有前 i 个字符，所以 dp[i][0] = sum(ascii(s1[0..i-1]))
  • dp[0][0] = 0

步骤4：计算顺序
从小到大计算 i 从 0 到 len(s1)，j 从 0 到 len(s2)

步骤5：答案
最终答案为 dp[len(s1)][len(s2)]

示例推导（s1="sea", s2="eat"）

  1. 初始化：

    • dp[0][0]=0, dp[1][0]=115, dp[2][0]=115+101=216, dp[3][0]=216+97=313
    • dp[0][1]=101, dp[0][2]=101+97=198, dp[0][3]=198+116=314

  2. 计算dp表：

    • i=1,j=1: s1[0]='s'(115)≠s2[0]='e'(101)
      dp[1][1]=min(115+dp[0][1], 101+dp[1][0])=min(115+101,101+115)=216

    • i=1,j=2: s1[0]≠s2[1]='a'(97)
      dp[1][2]=min(115+dp[0][2], 97+dp[1][1])=min(115+198,97+216)=min(313,313)=313

    • i=1,j=3: s1[0]≠s2[2]='t'(116)
      dp[1][3]=min(115+dp[0][3], 116+dp[1][2])=min(115+314,116+313)=min(429,429)=429

    • i=2,j=1: s1[1]='e'(101)=s2[0]='e'
      dp[2][1]=dp[1][0]=115

    • i=2,j=2: s1[1]='e'≠s2[1]='a'
      dp[2][2]=min(101+dp[1][2], 97+dp[2][1])=min(101+313,97+115)=min(414,212)=212

    • i=2,j=3: s1[1]='e'≠s2[2]='t'
      dp[2][3]=min(101+dp[1][3], 116+dp[2][2])=min(101+429,116+212)=min(530,328)=328

    • i=3,j=1: s1[2]='a'(97)≠s2[0]='e'
      dp[3][1]=min(97+dp[2][1], 101+dp[3][0])=min(97+115,101+313)=min(212,414)=212

    • i=3,j=2: s1[2]='a'=s2[1]='a'
      dp[3][2]=dp[2][1]=115

    • i=3,j=3: s1[2]='a'≠s2[2]='t'
      dp[3][3]=min(97+dp[2][3], 116+dp[3][2])=min(97+328,116+115)=min(425,231)=231

最终结果：dp[3][3]=231，与示例一致。

最长公共子序列的变种：两个字符串的最小ASCII删除和 题目描述 给定两个字符串 s1 和 s2 ，要求通过删除一些字符（可以删除任意字符串中的任意字符），使得两个字符串相等。每删除一个字符，就需要付出该字符的ASCII码值的代价。要求计算使两个字符串相等所需删除的最小ASCII码总和。 例如： 输入：s1 = "sea", s2 = "eat" 输出：231 解释： 删除 's' (ASCII 115) 来自 "sea" 得到 "ea" 删除 't' (ASCII 116) 来自 "eat" 得到 "ea" 使两个字符串相等的最小删除ASCII和为 115 + 116 = 231 解题思路 这个问题是最长公共子序列（LCS）的变种。在LCS中，我们寻找最长的公共子序列；而在这里，我们需要最小化删除的ASCII总和。实际上，最大化保留的公共子序列的ASCII总和，等价于最小化删除的ASCII总和（因为两个字符串的总ASCII和是固定的）。 步骤1：定义状态 定义 dp[i][j] 表示字符串 s1 的前 i 个字符（即 s1[0..i-1] ）和字符串 s2 的前 j 个字符（即 s2[0..j-1] ）的最小ASCII删除和。 步骤2：状态转移方程 考虑两种情况： 如果 s1[i-1] == s2[j-1] ，那么当前字符匹配，不需要删除，所以 dp[i][j] = dp[i-1][j-1] 。 如果 s1[i-1] != s2[j-1] ，那么我们可以选择删除 s1[i-1] 或删除 s2[j-1] ，取两者中较小的代价： 删除 s1[i-1] ：代价为 s1[i-1] 的ASCII值 + dp[i-1][j] 删除 s2[j-1] ：代价为 s2[j-1] 的ASCII值 + dp[i][j-1] 所以 dp[i][j] = min(ascii(s1[i-1]) + dp[i-1][j], ascii(s2[j-1]) + dp[i][j-1]) 步骤3：初始化 当 i=0 时， s1 为空，需要删除 s2 的所有前 j 个字符，所以 dp[0][j] = sum(ascii(s2[0..j-1])) 当 j=0 时， s2 为空，需要删除 s1 的所有前 i 个字符，所以 dp[i][0] = sum(ascii(s1[0..i-1])) dp[0][0] = 0 步骤4：计算顺序 从小到大计算 i 从 0 到 len(s1)， j 从 0 到 len(s2) 步骤5：答案 最终答案为 dp[len(s1)][len(s2)] 示例推导（s1="sea", s2="eat"） 初始化： dp[ 0][ 0]=0, dp[ 1][ 0]=115, dp[ 2][ 0]=115+101=216, dp[ 3][ 0 ]=216+97=313 dp[ 0][ 1]=101, dp[ 0][ 2]=101+97=198, dp[ 0][ 3 ]=198+116=314 计算dp表： i=1,j=1: s1[ 0]='s'(115)≠s2[ 0 ]='e'(101) dp[ 1][ 1]=min(115+dp[ 0][ 1], 101+dp[ 1][ 0 ])=min(115+101,101+115)=216 i=1,j=2: s1[ 0]≠s2[ 1 ]='a'(97) dp[ 1][ 2]=min(115+dp[ 0][ 2], 97+dp[ 1][ 1 ])=min(115+198,97+216)=min(313,313)=313 i=1,j=3: s1[ 0]≠s2[ 2 ]='t'(116) dp[ 1][ 3]=min(115+dp[ 0][ 3], 116+dp[ 1][ 2 ])=min(115+314,116+313)=min(429,429)=429 i=2,j=1: s1[ 1]='e'(101)=s2[ 0 ]='e' dp[ 2][ 1]=dp[ 1][ 0 ]=115 i=2,j=2: s1[ 1]='e'≠s2[ 1 ]='a' dp[ 2][ 2]=min(101+dp[ 1][ 2], 97+dp[ 2][ 1 ])=min(101+313,97+115)=min(414,212)=212 i=2,j=3: s1[ 1]='e'≠s2[ 2 ]='t' dp[ 2][ 3]=min(101+dp[ 1][ 3], 116+dp[ 2][ 2 ])=min(101+429,116+212)=min(530,328)=328 i=3,j=1: s1[ 2]='a'(97)≠s2[ 0 ]='e' dp[ 3][ 1]=min(97+dp[ 2][ 1], 101+dp[ 3][ 0 ])=min(97+115,101+313)=min(212,414)=212 i=3,j=2: s1[ 2]='a'=s2[ 1 ]='a' dp[ 3][ 2]=dp[ 2][ 1 ]=115 i=3,j=3: s1[ 2]='a'≠s2[ 2 ]='t' dp[ 3][ 3]=min(97+dp[ 2][ 3], 116+dp[ 3][ 2 ])=min(97+328,116+115)=min(425,231)=231 最终结果：dp[ 3][ 3 ]=231，与示例一致。