712. Minimum ASCII Delete Sum for Two Strings

又是dp题目

题目:删掉两个字符串中的字符让两个字符串相同,并统计删掉的字符的ascii码总和,要求总和最低。

思路:也是动态规划,和最长公共子序列很像,是个变种。
有两种思路,第一种:继续按照最长公共子序列来做,算出了最长公共子序列之后,拿两个字符串的ascii码总和减去公共子序列的ascii码值,就是去掉的字符串的ascii码的和;第二种:反向算最长公共子序列,当dp计算的时候,如果字符不相等,进行ascii码的计算,相等则继续循环。

我采用的是第二种思路,用的递归写法,个人认为递归的写法比较简单,一下就能开写,不太需要思考。

class Solution:
    def __init__(self):
        self.cache = []

    def minimumDeleteSum(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        self.cache = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]
        return self.dp(s1, s2, 0, 0)


    def dp(self, s1, s2, i, j):
        if i == len(s1) or j == len(s2):
            return self.cal(s1[i:]) + self.cal(s2[j:])
        elif s1[i] == s2[j]:
            return self.dp(s1, s2, i + 1, j + 1)
        elif self.cache[i][j] != 0:
            return self.cache[i][j]
        else:
            self.cache[i][j] = min(self.dp(s1, s2, i, j + 1) + ord(s2[j]), self.dp(s1, s2, i + 1, j) + ord(s1[i]))
            return self.cache[i][j]
            return self.cache[(i, j)]

    def cal(self, string):
        rsum = 0
        for i in string:
            rsum += ord(i)
        return rsum
分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注