代码随想录算法训练营Day54 | 392.判断子序列、115.不同的子序列 | Python | 个人记录向

392.判断子序列

代码随想录：392.判断子序列
Leetcode：392.判断子序列

做题

借鉴Day53中1143.最长公共子序列的思路，最后改一下判断逻辑即可。

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

时间复杂度：O(n × m)
空间复杂度：O(n × m)

看文章

思路一致。

115.不同的子序列

代码随想录：115.不同的子序列
Leetcode：115.不同的子序列

做题

无思路。

看文章

这道题很难，题解也看了很久。
动规五部曲：

1. 确定dp数组（dp table）以及下标的含义。

   dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

2. 确定递推公式。这一类问题，基本是要分析两种情况：

   s[i - 1] 与 t[j - 1]相等，dp[i][j]可以有两部分组成。
   一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
   另一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]，相当于复制直接的结果。

   s[i - 1] 与 t[j - 1] 不相等，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]。

3. dp数组如何初始化。

   dp[i][0]：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。

   dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0，s如论如何也变成不了t。

4. 确定遍历顺序。

   外部遍历 s，内部遍历 t。

5. 举例推导dp数组。

代码如下：

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] = 1for 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[len(s)][len(t)]

以往忽略的知识点小结

• 回到动规五部曲的基本思路，特别是dp数组的含义

个人体会

完成时间：1h30min。
心得：115.不同的子序列比较难，看了好久，需要回归到动规五部曲的基本思路，特别是dp数组的含义。

​