数据结构与算法：动态规划dp：子序列相关力扣题（下）：392. 判断子序列、115.不同的子序列

392. 判断子序列

1.套最长公共子序列问题的板子

class Solution:def isSubsequence(self, s: str, t: str) -> bool:"""最长公共子序列长度是否=len(s)，是就是true，否就是falsedp[i][j]考虑以s[i-1]，t[j-1]的最长公共子序列长度"""n = len(s)m = len(t)dp = [[0] * (m+1) for _ in range(n+1)]for i in range(1, n+1):for j in range(1, m+1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1]+1else:dp[i][j] = dp[i][j-1]return dp[n][m]==n

效率：19ms，击败16.26%

代码简单是简单，就是效率太低了。我们不需要使用两重循环来遍历两个字符串，而是直接双指针一起遍历即可。

2.双指针优化

class Solution:def isSubsequence(self, s: str, t: str) -> bool:i, j = 0, 0  # 双指针分别指向s和t的起始位置n, m = len(s), len(t)while i < n and j < m:if s[i] == t[j]:i += 1  # 匹配成功，移动s指针j += 1  # 无论是否匹配，都要移动t指针return i == n  # 检查是否匹配完所有s的字符

效率：0ms，击败100.00%

115.不同的子序列（hard）

题目的意思其实就是s如何删除元素能变成t

class Solution:def numDistinct(self, s: str, t: str) -> int:"""dp[i][j] = 一直考虑到以s[i-1]结尾的s中有多少子序列能成为一直考虑到以t[j-1]结尾的t"""n = len(s)m = len(t)dp = [[0] * (m+1) for _ in range(n+1)]# 要注意！这里相当于s只有一个元素，t为空字符串时，s有多少子序列能成为空字符串，所以为1for i in range(n+1):dp[i][0] = 1for i in range(1, n+1):for j in range(1, m+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[n][m]

效率：467ms，击败28.72%