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 caseif i == len(text1):while j < len(text2):res += ord(text2[j])j += 1return resif j == len(text2):while i < len(text1):res += ord(text1[i])i += 1return 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]