如何find一个string的不同子序列的数量？

这是另一个问题 ，如何find一个string的不同子序列的数量？

例如，

input
AAA
ABCDEFG
CODECRAFT

产量
4
128
496

我怎么解决这个问题 ？

Answer 1

这是一个经典的dynamic编程问题。

让：

dp[i] = number of distinct subsequences ending with a[i] sum[i] = dp[1] + dp[2] + ... + dp[i]. So sum[n] will be your answer. last[i] = last position of character i in the given string. 

一个空string有一个子序列，所以dp[0] = 1 。

 read a n = strlen(a) for i = 1 to n dp[i] = sum[i - 1] - sum[last[a[i]] - 1] sum[i] = sum[i - 1] + dp[i] last[a[i]] = i return sum[n] 

说明

 dp[i] = sum[i - 1] - sum[last[a[i]] - 1] 

最初，我们假设我们可以将a[i]追加到以前的字符结尾的所有子序列，但是这可能违反了被计数的子序列需要不同的条件。 请记住， last[a[i]]给了我们迄今为止出现的最后一个位置。 我们唯一的子序列是先前的a[i]被追加到的那些，所以我们减去那些。

 sum[i] = sum[i - 1] + dp[i] last[a[i]] = i 

按照他们的定义更新这些值。

如果索引从0开始， a[i - 1]在我使用a[i]地方使用a[i - 1] a[i] 。 如果您要提交代码，请记住在mod函数中包含您的计算。 这应该像这样实现：

 mod(x) = (x % m + m) % m 

为了正确处理某些语言的负值（如C / C ++）。

Answer 2

这个问题有一个更简单的解决scheme。

这个想法是：如果string的所有字符都是不同的，则子序列的总数是2^n. 现在，如果我们发现之前已经发生的任何字符，我们应该只考虑它的最后一次出现（否则序列将不明显）。 所以我们必须减去前一次出现的子序列的数量。

我的实现是这样的：

 read s dp[0] = 1 len = strlen(s) for (i = 1; i <= len; i++) { dp[i] = (dp[i - 1] * 2) if (last[s[i]] != 0) dp[i] = (dp[i] - dp[last[s[i]] - 1]) last[s[i]] = i } 

Answer 3

 ///i get wa int finding_dist_subs(int len,char data[]) { dp[0]=1; for(int i=1;i<len;i++) { dp[i]=(dp[i-1]*2+1)%1000000007; for(int j=i-1;j>=0;j--) { if(data[i]==data[j]) { if(j!=0) dp[i]=(dp[i]-(dp[j-1])-1)%1000000007; else dp[i]=(dp[i]-1)%1000000007; break; } } } return dp[len-1]; }