题目

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

注意:

0 < s1.length, s2.length <= 1000。
所有字符串中的字符ASCII值在[97, 122]之间。

解答

学会动态规划的解法，对解决数组或字符串类型的问题是很有帮助的。动态规划的数组定义和递推关系是其核心，大问题分解为小问题是核心思想，用空间代替时间是其效率提高的主要原因。

【数组定义】设输入字符串分别为s1和s2，长度分别为l1和l2，定义二维数组dp，维度为(l1+1)x(l2+1)，对于其中任意一个元素dp[i][j]表示字符串s1[:i]与字符串s[:j]的最小ascii删除和，相当于截取s1前i个字符的子串与s2前j个字符的子串，两个子串进行比较，因为i和j都有可能为零，因此在两个维度上都增加了1。

【初始状况】我们可以先把i=0或者j=0的状态填写在数组中。当i=0时，s1[:i]是空串，dp[0][j]实际上是s2[:j]子串所有字母的ascii和（因为需要把所有字母都去掉，才能等于空串），同样的，当j=0时，也可以用来类似的方式处理。这样，就先把dp数组的左上角的两条边填好了。

【递推公式】需要考虑两种情况，如果s1子串和s2子串的最后一个字母是相同的，也就是s1[i] == s2[j]，那么可以直接填充：dp[i+1][j+1] = dp[i][j]。
否则，需要进行比较，比较去掉s1[i]和去掉s1[j]哪个代价更大，然后选择其中的最优项。这里需要注意，python中的下标是从0开始的，与物理意义需要进行一个加减1的换算。

【最终状态】最后返回dp数组最右下角的元素即可。

class Solution(object):
    def minimumDeleteSum(self, s1, s2):
        dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

        for i in range(len(s1)):
            dp[i+1][0] = dp[i][0] + ord(s1[i])
        for j in range(len(s2)):
            dp[0][j+1] = dp[0][j] + ord(s2[j])

        for i in range(len(s1)):
            for j in range(len(s2)):
                if s1[i] == s2[j]:
                    dp[i+1][j+1] = dp[i][j]
                else:
                    dp[i+1][j+1] = min(dp[i][j+1] + ord(s1[i]),
                                   dp[i+1][j] + ord(s2[j]))

        return dp[-1][-1]

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析