发表于 2024.04.18

• 带权重的编辑问题，其中删除一个字符的成本为字符的ASCII值。令dp[i][j]为子串s1[:i]和s2[:j]的最小编辑距离：如果s1[i - 1]等于s2[j - 1]，则dp[i][j] = dp[i - 1][j - 1](两字符串该字符无需修改)，否则dp[i][j] = min(dp[i][j - 1] + ord(s2[j - 1]), dp[i - 1][j] + ord(s1[i - 1]))(删除s1[:i]的最后一个字符的代价 + 子串s1[:i - 1]和s2[:j]的累积代价 or 删除s2[:j]的最后一个字符的代价 + 子串s1[:i]和s2[:j - 1]的累积代价)。

  class Solution:
      def minimumDeleteSum(self, s1: str, s2: str) -> int:
          # dp[i][j] -> s1[:i]和s2[:j]的编辑距离
          dp = [[0] * (len(s2) + 1) for _ in range((len(s1) + 1))]
          for i, ch in enumerate(s1):
              dp[i + 1][0] = dp[i][0] + ord(ch)
          for i, ch in enumerate(s2):
              dp[0][i + 1] = dp[0][i] + ord(ch)
          for i in range(1, len(s1) + 1):
              for j in range(1, len(s2) + 1):
                  c1 = s1[i - 1]
                  c2 = s2[j - 1]
                  if c1 == c2:
                      dp[i][j] = dp[i - 1][j - 1]
                  else:
                      dp[i][j] = min(
                          dp[i - 1][j] + ord(c1),
                          dp[i][j - 1] + ord(c2)
                      )
          return dp[len(s1)][len(s2)]

• LC 题目链接