动态规划15 | ● 392.判断子序列 ● *115.不同的子序列

392.判断子序列

https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

• 考点
  • 子序列问题
• 我的思路
  • dp[i][j]的含义是，两个序列分别取到下标为i和j的时候，他们是否满足前者是后者的子序列，满足为True，否则为False
  • 递推公式，分为后者序列取到第j - 1个元素时就已经满足前者序列为其子序列的情况、dp[i - 1][j - 1]满足子序列要求且前者序列的第i个元素和后者序列的第j个元素恰好相等的情况、以及dp[i][j]不满足为子序列的情况
  • 初始化，建议画出二维矩阵，并举一个例子来分析，仅额外初始化后者序列对应的第一条边即可（将所有满足子序列要求的位置设置为True），其与都为False
• 视频讲解关键点总结
  • 和我的思路不太一样
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

class Solution:def isSubsequence(self, s: str, t: str) -> bool:if s == '':return Trueelif t == '':return Falsedp = [[False] * len(t) for _ in range(len(s))]for i in range(len(t)):if t[i] == s[0]:for j in range(i, len(t)):dp[0][j] = Truebreakfor i in range(1, len(s)):for j in range(1, len(t)):if dp[i][j - 1]:dp[i][j] = Trueelif s[i] == t[j] and dp[i - 1][j - 1]:dp[i][j] = Truereturn dp[-1][-1]

*115.不同的子序列

https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

• 考点
  • 子序列问题
• 我的思路
  • 无思路
• 视频讲解关键点总结
  • 明确本题的目标，我们是要在后者元素中删除元素获得子序列来让该子序列与前者序列相同
  • dp[i][j]的含义是，两个序列分别取到下标为i和j的时候，后者序列能组合出多少种和前者序列相同的子序列
  • 递推公式，如果当前下标的元素相同，则可以同时取当前下标元素（此时dp[i][j] = dp[i - 1][j - 1]）或者不取后者序列的当前元素（此时dp[i][j] = dp[i][j - 1]）；如果当前下标的元素不相同，则只有dp[i][j] = dp[i][j - 1]
  • 初始化，建议画出二维矩阵，并举一个例子来分析，仅额外初始化后者序列对应的第一条边即可
• 我的思路的问题
  • 无思路
• 代码书写问题
  • 无
• 可执行代码

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