C ++中的不同子序列II
假设我们有一个字符串S，我们必须计算S的不同子序列数。结果可能很大，因此我们将以10^9+7为模返回答案。
因此，如果输入像“bab”，那么输出将为6，因为有6个不同的序列，分别是“a”，“b”，“ba”，“ab”，“bb”，“abb”。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数add()，这将需要a，b，
返回（（amodMOD）+（bmodMOD））modMOD
定义一个函数sub()，这将需要a，b，
返回（（（（amodMOD）-（bmodMOD））+MOD）modMOD
定义一个函数mul()，这将需要a，b，
返回（（amodMOD）*（bmodMOD））modMOD
从主要方法来看，所以以下内容-
n：=s的大小
定义大小为26的数组dp
res：=0
s：=在s之前连接空间
对于初始化i：=1，当i<=n时，更新（将i增加1），-
x：=s[i]
添加：=sub（add(res,1)，dp[x-'a']）
dp[x-'a']=add（dp[x-'a']，已添加）
res：=添加（res，添加）
返回资源
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % MOD) + (b % MOD) ) % MOD;
}
lli sub(lli a, lli b){
return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
}
lli mul(lli a, lli b){
return ( (a % MOD) * (b % MOD) ) % MOD;
}
int distinctSubseqII(string s) {
int n = s.size();
vector <lli> dp(26);
int res = 0;
s = " " + s;
for(lli i = 1; i <= n; i++){
char x = s[i];
int added = sub(add(res, 1) , dp[x - 'a']);
dp[x - 'a'] = add(dp[x - 'a'], added);
res = add(res, added);
}
return res;
}
};
main(){
Solution ob;
cout << (ob.distinctSubseqII("bab"));
}输入值
"bab"
输出结果
6