现代网站建设,手机网页无法访问,云岭建设集团的网站,免费代理网页题干#xff1a;
力扣 解题报告#xff1a;
dp[i]代表以s[i]结尾的子序列数量。
然后再加一层循环枚举倒数第二个字符。
dp之后考虑去重#xff08;或者直接再用一个数组cnted[26]表示a~z字符结尾的子序列已经有多少个了#xff09;然后直接作差就可以#xff0c;因为…题干
力扣 解题报告
dp[i]代表以s[i]结尾的子序列数量。
然后再加一层循环枚举倒数第二个字符。
dp之后考虑去重或者直接再用一个数组cnted[26]表示a~z字符结尾的子序列已经有多少个了然后直接作差就可以因为不难证明cnted[s[i]-a]统计的是dp[i]的真子集所以所有s[i]结尾的都可以减去。
AC代码
class Solution {
public:int p[20005][26];long long dp[20005];const int mod 1e9 7;int distinctSubseqII(string s) {memset(p[0], -1, sizeof(p[0]));p[0][s[0]-a] 0;for(int i 1; is.size(); i) {for(int j 0; j26; j) {if(j s[i]-a) p[i][j] i;else p[i][j] p[i-1][j];}}dp[0]1;for(int i 1; is.size(); i) {dp[i] 1;for(int j 0; ji; j) {if(s[j] ! s[i]) dp[i] dp[j];}dp[i] % mod;}int ans 0;for(int i 0; is.size(); i) {ans (ans dp[i])%mod;}return ans;}
};
