给定一个数组a(可能包含相同的数),求它有多少个不同的子序列。例如a={1,2,1,3}子序列有{1}{2}{3}{
给定一个数组a（可能包含相同的数），求它有多少个不同的子序列。例如a={1,2,1,3}子序列有{1}{2}{3}{1,2}{1,3}{1,2}{1,1}{1,3}{2,1}{2,3}{1,2,1}{1,2,3}{1,1,3}{2,1,3}等。
正确答案：这个题本身不难，但是分析清楚不容易。我们首先假设子序列可以为空——最后减1就好了。假设dp[i]表示数列前i项构成的不同子序列的个数。初值：dp[0]=1因为只有一个空子序列我们现在考虑dp[i]（1）如果数列第i项在之前没有出现过，是一个新数显然dp[i]=dp[i-1]*2这是因为前(i-1)项的子序列本身，以及添加上第i项，都是一个子序列，这是比较容易的情况。如果全是这样，人生就完美了……因为我们会推出dp[i]=2^i，但还有讨厌的第二种情况。（2）如果第i项在之前出现过，假设j是它最近一次出现的
词条内容仅供参考，如果您需要解决具体问题
（尤其在法律、医学等领域），建议您咨询相关领域专业人士。