LeetCode/不同的子序列II
给定一个字符串 s，计算 s 的 不同非空子序列 的个数
1. 动态规划(记录位置去重)
设dp[i]为以i位置结尾的子序列数目，方便状态的转移
dp[i]= sum(dp[j]) ，j为上一次该字母出现位置到这一次字母出现的所有位置，从上一次出现位置开始主要为了去重
其实就是把该字母拼接到前面这些右边界确定的子序列上，形成新的子序列
同时要考虑该字母之前有没有出现过，否则其本身也可以作为一个子序列，即一开始dp[i]=1
class Solution {
public:
int distinctSubseqII(string s) {
//dp[i]表示以i为尾的子序列数目
int mod_ = pow(10,9)+7;
int sum = 0;//对所有边界子序列求和
vector dp(s.size());
vector map_(26,-1);//记录上一个26字母初始位置
for(int i=0;i 2. 动态规划优化（记录字符去重）
在方法一中，计算上一次该字母到该字母所有位置的子序列和，其实就是对以该字母结尾的子序列做了更新
设dp[i]是以字符i结尾的子序列数目，考虑新字符对所有类型字符拼接即可，同样起到了去重作用
状态转移方程dp[i] = sum(dp[j]) ，j为所有字符
class Solution {
public:
int distinctSubseqII(string s) {
vectordp(26,0); //初始化容器为0
int mod=1e9+7;
for(auto& ch:s){
dp[ch-'a']=accumulate(dp.begin(),dp.end(),1l)%mod; //遍历字符串更新dp数组
}
return accumulate(dp.begin(),dp.end(),0L)%mod;//求和
}
};
3. 动态规划(记录位置优化)
其实也就是找规律，省去了方法一求和的步骤
class Solution {
public:
int distinctSubseqII(string s) {
//找规律
int len = s.size();
int mod_ = pow(10,9)+7;
vector dp(len+1);
dp[0] = 1;
vector map_(26,-1);//记录上一个26字母初始位置
for(int i=0;i=0) dp[i+1]=(dp[i+1]-dp[index])%mod_;
map_[s[i]-'a'] = i;//更新该字母索引
}
dp[len]--;
if(dp[len]<0) dp[len]+=mod_;
return dp[len];
}
};