算法day55|392，115

392.判断子序列

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        #定义dp数组,dp[i][j],i为s,j为t
        dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+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]+1
                else:
                    dp[i][j] = dp[i][j-1]
        if dp[-1][-1] == len(s):
            return True
        return False

dp数组的含义dp[i][j]

i-1的字符串s的子序列。j-1的字符串t的子序列。dp[i][j]代表相同子序列的长度。

递归公式

分两种情况：当s[i-1] == t[j-1]的时候，dp[i-1][j-1]前面的长度的集合+1

当s[i-1] != t[j-1]的时候，删除t,那么剩下的就是s-1和t-2 开始比较，dp= dp[i][j-1]

初始化

初始化为0，因为有可能没有相同子序列。

如果最后的长度与s字符串的相等的话，说明是true

代码随想录

115.不同的子序列

dp数组的定义

这个dp数组的定义都很难。

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

就是说，假设s 中"b"匹配t中的“b"，看有多少个。

递归公式

如果s[i-1]和t[j-1]相等，

可以由两个部分组成，第一个部分是使用s[i-1]来匹配。

dp[i][j] = dp[i-1][j-1]

为什么不是不用加一呢？？？？？不是又匹配上了吗?

第二个是不使用s[i-1]来匹配。dp[i-1][j]跳了下一个匹配。

s[i-1]和t[j-1]不相等：

只能跳下一个匹配

所以还是dp[i][j] = dp[i-1][j]

初始化

dp[i][0]代表用空来匹配s，所以都为1.

dp[0][j]代表t匹配空，所以都是为0

dp[0][0]，空配空，所以为1

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        #dp数组,dp[i][j]
        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
        #初始化
        for i in range(len(s)):dp[i][0] = 1
        for j in range(1,len(t)):dp[0][j] = 0
        for i in range(1,len(s)+1):
            for j in range(1,len(t)+1):
                if s[i-1] == t[j-1]:
                    #用s[i-1]来匹配，和不用s[i-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]

代码随想录