leetcode题解115：不同的子序列

描述

该题来自于力扣第115题

分析

这种问题应该首先想到动态规划是否可以解决，以dp[i][j]表示s[:i]的子序列中t[:j]出现的个数，然后看看转移方程是什么？

当s[i-1] = t[j-1]时，有两种情况：1. 不算上s[i-1]，即s[:i-1]的子序列中t[:j]出现的个数dp[i-1][j]；2. 算上s[i-1]，即s[:i-1]中的子序列中t[:j-1]出现的个数dp[i-1][j-1]；两种情况相加。

否则就是s[:i-1]的子序列中t[:j]出现的个数dp[i-1][j]。

所以转移方程为
\[ dp[i][j] = \left\{ \begin{aligned} & dp[i-1][j] + dp[i-1][j-1] & s[i-1]=t[j-1]\\ & dp[i-1][j] & others \end{aligned} \right. \]

可以看到dp[i][?]只与dp[i-1][?]状态有关，从而可以状态压缩，使用一维数组表示，所以

dp[k] = dp[k] + dp[k-1] * (s[i-1] == t[j-1]) ? 1 : 0

又由于dp[k]需要使用dp[k-1]的状态，所以k从后面开始更新，而初始状态dp[0]=1，其他设为0。

代码

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0

        dp = [0 for _ in range(len(t)+1)]
        dp[0] = 1
        for i in range(1, len(s)+1):
            for j in range(len(t), 0, -1):
                if s[i-1] == t[j-1]:
                    dp[j] += dp[j-1]
        return dp[len(t)]