先上demon（代碼）
class Solution {
public:
int distinctSubseqII(string s) {
long long harsh[2001][150]={0};
long long count[2001]={0};
count[0]=1;
for(char i='a';i<='z';i++)
harsh[0][(int)i]=1;
for(int i=0;i<s.length();i++){
for(int j=i;j>=0;j--){
if(harsh[j+1][(int)s[i]]==0){
count[j+1]+=count[j]%(1000000007);
count[j+1]=count[j+1]%(1000000007);
harsh[j+1][(int)s[i]]=count[j]%(1000000007);
harsh[j+1][(int)s[i]]%=1000000007;
}else{
count[j+1]=count[j+1]%(1000000007)+count[j]%(1000000007)-harsh[j+1][(int)s[i]]%(1000000007);
count[j+1]%=1000000007;
harsh[j+1][(int)s[i]]+=count[j]%(1000000007)-harsh[j+1][(int)s[i]]%(1000000007);
harsh[j+1][(int)s[i]]%=1000000007;
}
}
}
long long int res=0;
for(int i=0;i<s.length();i++){
res+=count[i+1]%(1000000007);
res%=1000000007;
}
return res%(1000000007);
}
};
請無視那一堆百分號1000……7
不同的子序列 長得很像動態規劃
那么，該怎么猜呢
首先，不管同不同，原長度為len的一個序列，末尾添加一個字母比如x
那么就會多出來1+L1+L2+……+Llen個序列（其中Ln是長度為n的序列總數）
那所以啊，只要去掉重復的不就行了
外層回圈用來遍歷s中的字母
下一層回圈
用一個哈希表 harsh[序列長度][最后一個字母] harsh[len][x]代表以x為最后字母的，長度為len的不同的序列總數，count[len]代表長度len的不同的序列總數，
因此有以下的關系：
如果harsh[len][x]==0 那么count[len]的更新就直接加上count[len-1]就可以了
同時記得更新harsh[len][x]=count[len-1]//增加了count[len-1]個以x為結尾的長度為len的不同序列
如果harshlenx不是0，也就是出現過，那么稍微復雜一點
count[len]+=count[len-1]-harsh[len][x]//增加了count[len-1]個以x結尾的序列，但是之前有harsh[len][x]個已經出現過了，重復了，需要減去，
harsh[len][x]更新同理 +=count[len-1]-harsh[len][x]//把新增加的加進去；
小結一下
就是考慮新增加的字母，對以前的序列產生的影響，可以帶來的變化
因此回圈的順序就很重要了，因為count[x]=…count[x-1]……可以看出應該先計算countx
所以第二重回圈是倒過來的
當然你也可以正著寫，只不過把count換成二維~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/400468.html
標籤：其他