712. 两个字符串的最小ASCII删除和 -- 动规

712. 两个字符串的最小ASCII删除和

class MinimumDeleteSum:
    """
    712. 两个字符串的最小ASCII删除和
    https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
    """
    def solution(self, s1: str, s2: str) -> int:
        """
                递归解法 + 备忘录
                自顶向下
                :param text1:
                :param text2:
                :return:
                """
        m, n = len(s1), len(s2)
        self.memo = [[-1 for _ in range(n)] for _ in range(m)]

        return self.dp(s1, 0, s2, 0)

    def dp(self, text1, i, text2, j):
        """
        将 s1[i..] 和 s2[j..] 删除成相同字符串
        :param text1:
        :param i:
        :param text2:
        :param j:
        :return:
        """
        res = 0
        # base case
        if i == len(text1):
            while j < len(text2):
                res += ord(text2[j])
                j += 1
            return res
        if j == len(text2):
            while i < len(text1):
                res += ord(text1[i])
                i += 1
            return res

        # 备忘录
        if self.memo[i][j] != -1:
            return self.memo[i][j]

        if text1[i] == text2[j]:
            self.memo[i][j] = self.dp(text1, i + 1, text2, j + 1)
        else:
            self.memo[i][j] = min(self.dp(text1, i + 1, text2, j) + ord(text1[i]),
                                  self.dp(text1, i, text2, j + 1) + ord(text2[j]))

        return self.memo[i][j]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54