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