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

392. 判断子序列

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

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        """
        最长公共子序列长度是否=len(s)，是就是true，否就是false
        dp[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]+1
                else:
                    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有多少子序列能成为空字符串，所以为1
        for i in range(n+1):
            dp[i][0] = 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]+dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][m]

效率：467ms，击败28.72%