面试题：数组中子序列的个数

数组中子序列的个数

题目描述：

给定一个数组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是它最近一次出现的位置，我们有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因为我们考虑了空的子序列。

还有一种分析可以不考虑空的子序列，也是类似的。

 

就业班来了

依据个人情况定制化教学

名企面试官亲自辅导面试

让你“薪”满意足！

加送售价3299元的新VIP

[包未来一年在线课程和全年GPU]

间谍用GAN制造“红发美女”！潜入美国政坛，轻松钓政客

数学差，连机器学习都做不了吗？

戳 “阅读原文”查看课程一起进步！

你在看吗？