参考答案

正确答案：

这个题本身不难，但是分析清楚不容易。我们首先假设子序列可以为空——最后减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是它最近一次出现的位置，我们有0<j<i（注意i,j都是项数，或者说下标从1开始的）那么我们直接乘以2，有些会重复。哪些重复了呢？原来的前(j-1)项的子序列末尾添加上第j项和添加上第i项是一样的，就这些是重复的。所以dp[j-1]是重复的。此时dp[i]=dp[i-1]*2-dp[j-1]最后千万别忘记答案是dp[n]-1因为我们考虑了空的子序列。还有一种分析可以不考虑空的子序列，也是类似的。