Leecode #115 不同的子序列

难度：hard

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例

输入：S = "rabbbit", T = "rabbit"
输出：3
解释：

如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

解题思路

​ 算是很经典的动态规划题了，d[i, j]表示s的前i个字符含有t前j个字符子序列的个数。

当s[i]==t[j]计算两种情况的和：

• 保持s[i]和t[i]对应，有d[i-1，j-1]个子序列
• s[i]和t[i]不对应，即在s[i]出现之前，已经有d[i，j-1]个子序列

当s[i]!=t[j]时：

• d[i,j]=d[i,j-1]

因此可以得到代码

def numDistinct(self, s: str, t: str) -> int:
        s = '_'+s
        t = '_'+t
        l1 = len(s)
        l2 = len(t)
        if l1 < l2:
            return 0

        arr = [[0] * l1 for i in range(l2)]
        for i in range(l1):
            arr[0][i] = 1
        for i in range(1, l2):
            for j in range(i, l1):
                if s[j] == t[i]:
                    arr[i][j] = arr[i][j-1]+arr[i-1][j-1]
                else:
                    arr[i][j] = arr[i][j-1]
        return arr[-1][-1]
# 用时 212ms 内存 28.1mb

然而这道题的经典在于其优化过程，如上代码，我们申请了一个二维的数组，有没有办法减少我们的空间占用呢？我们看到d[i,j]取决于其上一位和左边一位的值，那么我们只用申请一个一维的数组，并用两个变量保存每次迭代时左边和上面的那个数值：

def numDistinct(self, s: str, t: str) -> int:
        s = '_'+s
        t = '_'+t
        l1 = len(s)
        l2 = len(t)
        if l1 < l2:
            return 0
        arr = [1] * l1

        for i in range(1, l2):
            last = 0
            upper = 0
            for j in range(i, l1):
                temp = arr[j]
                if s[j] == t[i]:
                    arr[j] = arr[j-1] + upper
                else:
                    arr[j] = last
                last = arr[j]
                upper = temp
        return arr[-1]
# 用时 112 ms 内存消耗 13.7mb

还有一个更加变态的版本，不过我目前还没搞懂，先贴一下代码

    def numDistinct(self, s: str, t: str) -> int:
        dp = [0]*(len(t)+1)
        dp[0]=1
        for i in range(len(s)):
            for j in range(len(t),0,-1):
                if s[i]==t[j-1]:
                    dp[j] += dp[j-1]
        return dp[-1]
# 用时 88ms 内存消耗 13.7mb