leetcode p940不同的子序列
先上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换成二维~