动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

考点
- 子序列问题
我的思路
- dp[i][j]的含义是，当两个字符串分别取前i和j个元素时，对应的最少相等删除步数是多少
- 递推公式为，如果两个字符串第i和j个元素恰好相等，则dp值应等于不再考虑这两个元素的dp值即dp[i - 1][j - 1]；如果i和j不相等，则dp值应等于删除任一元素后的dp值取较小者即min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
- 初始化，由于递推公式依赖于当前元素在二维矩阵中的左上元素，因此需要对二维矩阵的第一行和第一列进行初始化，初始化原则是，如果当前位置两字符串的元素相等，则dp等于将较长者除当前元素外其它元素均删除所需要的步数；如果不相等，dp等于不考虑较长字符串当前元素后所需要的最少步数和不考虑较短字符串当前元素（也就是令较短字符串为空）时所需要的最少步数中取较小者
视频讲解关键点总结
- 和我的思路一致
我的思路的问题
- 无
代码书写问题
- 无
可执行代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * len(word2) for _ in range(len(word1))]
        if word1[0] == word2[0]:
            dp[0][0] = 0
        else:
            dp[0][0] = 2
        for i in range(1, len(word1)):
            if word1[i] == word2[0]:
                dp[i][0] = i
            else:
                dp[i][0] = min(dp[i - 1][0] + 1, i + 2)
        for i in range(1, len(word2)):
            if word1[0] == word2[i]:
                dp[0][i] = i
            else:
                dp[0][i] = min(dp[0][i - 1] + 1, i + 2)
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
        return dp[-1][-1]

*72. 编辑距离

https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html文章来源地址https://www.toymoban.com/news/detail-855621.html

考点
- 子序列问题
我的思路
- dp含义和上一题整体思路相同
- 递推公式两元素相等的情况和上一题相同，但是两元素不相等的情况只考虑到了删除当前word1元素的解法
- 初始化较为简单，不展开说了
视频讲解关键点总结
- 我的思路的问题就在，递推公式里，如果两元素不相等，应该有三种处理方式（增、删、改），而我只实现了删的操作，其中增加一个元素也就是增加和word2当前元素相同的元素，也就是不需要考虑word2当前元素；删除也就是不考虑word1当前元素；改也就是不需要考虑word1和word2的当前元素
我的思路的问题
- 漏了两种情况
代码书写问题
- 无
可执行代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if word1 == '' and word2 == '':
            return 0
        elif word1 == '':
            return len(word2)
        elif word2 == '':
            return len(word1)
        dp = [[0] * len(word2) for _ in range(len(word1))]
        if word1[0] == word2[0]:
            dp[0][0] = 0
        else:
            dp[0][0] = 1
        for i in range(1, len(word1)):
            if word1[i] == word2[0]:
                dp[i][0] = i
            else:
                dp[i][0] = dp[i - 1][0] + 1
        for i in range(1, len(word2)):
            if word1[0] == word2[i]:
                dp[0][i] = i
            else:
                dp[0][i] = dp[0][i - 1] + 1
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1)
        return dp[-1][-1]