LeetCode-940 Distinct Subsequences II

题目链接

题意

求S的不重复子序列个数

思路

DP

详解

显然如果S的每个字符都是不同的，一共有\(2^{n}\)个子集（子序列），用dp[i]表示第i位的子序列个数，则有dp[i+1]=2*dp[i]

考虑重复情况，如果第i位的字母之前出现过，设最近的出现位置是j，则j-1的情况会被多计一次，减掉就行了

详细解释下为什么：

首先，dp[i+1]=2*dp[i]的转移方程基于乘法原理：取了这个字母与没取这个字母两种情况

那么，由于S[i]==S[j]，重复的情况是“没取S[j]取了S[i]”和“取了S[j]没取S[i]”，仔细思考，这两种情况都需要在j后面的字母都没有取，否则也不是重复，所以这种情况一共dp[j-1]种

PS：别忘了减掉空集

PPS：模运算下的减法需要(a-b+mod)%mod

代码

class Solution:
    def distinctSubseqII(self, S):
        dp = [0] * (len(S)+1)
        dp[0] = 1
        mk = [0] * 26
        MOD = 1000000007
        for (i, ch) in enumerate(S, 1):
            idx = ord(ch)-ord('a')
            if(mk[idx]!=0):
                dp[i] = (dp[i-1] * 2 - dp[mk[idx]-1] + MOD)%MOD
            else:
                dp[i] = (dp[i-1] * 2)%MOD
            mk[idx] = i
        return dp[len(S)] - 1