583. 两个字符串的删除操作 -- 动规

583. 两个字符串的删除操作

class MinDistance:"""583. 两个字符串的删除操作https://leetcode.cn/problems/delete-operation-for-two-strings/description/"""def solution(self, text1: str, text2: str) -> int:"""这道题删除到最后的结果就是两个字符串的最长公共子序列，想到这里，问题迎刃而解:param text1::param text2::return:"""m, n = len(text1), len(text2)# dp[m][n] 表示 text1[0..m-1][0..n-1]的lcsdp = [[0 for _ in range(n+1)] for _ in range(m+1)]# base case# dp[0][...]   dp[...][0] = 0for i in range(1, m+1):for j in range(1, n+1):if text1[i-1] == text2[j-1]:dp[i][j] = 1 + dp[i-1][j-1]else:dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])lcs = dp[m][n]return m + n - 2 * lcs