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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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