代码随想录算法训练营第四十五天|leetcode115.不同的子序列、leetcode583. 两个字符串的删除操作、leetcode72. 编辑距离

1 leetcode115.不同的子序列

题目链接：115. 不同的子序列 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：动态规划之子序列，为了编辑距离做铺垫 | LeetCode：115.不同的子序列哔哩哔哩bilibili

思路：确实看不懂题目，还是看解析吧

1.1 视频后的方法

有一种我看了视频，也没有那么理解是为什么

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0]*(len(t)+1) for _ in range((len(s)+1))]
        for i in range(len(s)+1):
            dp[i][0] = 1
        for i in range(1,len(s)+1):
            for j in range(1,len(t)+1):
                if s[i-1]==t[j-1]:
                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

1.2 本题小结

1. 这个递推公式为什么是这样，其实自己画图了，也没有很能理解吧，但是知道这样最终的计算结果是正确的

2. 逐渐掌握吧，就是说，还是有点难度在这里的，这个题

2 leetcode583. 两个字符串的删除操作

题目链接：583. 两个字符串的删除操作 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：动态规划之子序列，还是为了编辑距离做铺垫 | LeetCode：583.两个字符串的删除操作哔哩哔哩bilibili

思路：其实感觉跟之前的题目，差不太多，就是有一种递推公式不断变换的感觉，但是我不会，只能看视频以后去摸索一下

2.1 一种很巧妙的思路

就是算出重复字符串的长度，将两个字符串的长度相加再除以重复字符串的长度，好像就能出结果了

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

2.2 视频的方法

看的时候属实有一点没明白是为什么，主要还是递推公式比较懵吧

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

2.3 本题小结

1. 主要就是dp[i][j]的含义吧，这里需要弄清楚，不然的话，就很容易混淆，第二个就是哪种是属于删除元素的操作，也需要很清楚

2. 这一块主要是这个问题，理解这个含义比较重要吧

3 leetcode72. 编辑距离

题目链接：72. 编辑距离 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：动态规划终极绝杀！ LeetCode：72.编辑距离哔哩哔哩bilibili

思路：这题目，不说做，我看着就不会了，不是我现在能尝试的那种感觉，但是还是去学习一下吧，没准下一次我就会了呢

3.1 视频后的思路

救命，感觉看视频有种智商被吊打的感觉，不过也有好消息，这个代码中每个含义，我也算是真的理解了吧

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

3.2 本题小结

1. 这个题目就是说，理解了含义以后，每种情况认真分析，还是可以写出来的

2. 就是主要是没理解，这几种情况之间到底什么关系，导致觉得这道题非常的难吧

4 今日小结

1. 终于，算是明白了一种新的题目吧，其实主要就是dp[i][j]的含义

2. 这一块就是主打一个递推公式的理解，慢慢的感觉好一点了吧，说实话现在虽然还会有问题，但是我的能力方面，提升的还是有些明显的，继续加油