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;
}
};