leetcode 困难题 940. Distinct Subsequences II 不同的子序列 II-耗时100

Problem: 940. Distinct Subsequences II 不同的子序列 II

耗时100%，动态规划的，考虑两种情况，每种字符都不相同，存在相同的字符，dp[i]表示s[0～i]子字符串的总数，若是s[0~i-1]不存在s[i]，那么结果就是dp[i] = (dp[i-1] * 2) + 1;也就是之前的所有子字符串最后面加上s[i]即可，以及包含了s[i]这个单个字符

若s[0~i-1]存在s[i]，假设s[j]s[i] (j < i)，那么s[0_{i-1]的子字符串s[j]可以被s[i]替代，相当于s[0}j-1]的子字符串添加上s[i]或s[j]，此时末尾加上s[i]或者s[j]效果相同，所以重复了一次，需要减去的也就是dp[i] = dp[i] - 1 - dp[j-1] + modulo; -1是单字符s[i]本身重复了一次，而且当j0时，需要特殊考虑此时dp[i] = dp[i] - 1 + modulo

考虑到dp[i] = dp[i] - 1 - dp[ind-1]可能<0，所以需要加上模1e9+7

Code

class Solution { public: int ch[26]; const long long modulo = 1e9 + 7; int distinctSubseqII(string s) { fill(ch, ch + 26, -1); int n = s.size(), ind; if(n==1) return 1; vector<long long> dp(n, 0); dp[0] = 1; ch[s[0]-'a'] = 0; for(int i = 1; i < n; i++) { dp[i] = (dp[i-1] << 1) + 1; ind = ch[s[i]-'a']; if(ind == 0) { dp[i] = dp[i] - 1 + modulo; } else if(ind > 0){ dp[i] = dp[i] - 1 - dp[ind-1] + modulo; } ch[s[i]-'a'] = i; dp[i] = dp[i] % modulo; } int ret = dp[n-1] % modulo; return ret; } };