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


文章来源:https://dwz.cn/Q6tQ4yiG

数组中子序列的个数

题目描述:

给定一个数组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因为我们考虑了空的子序列。

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

18.png


就业班来了

依据个人情况定制化教学

名企面试官亲自辅导面试

让你“薪”满意足!

加送售价3299元的新VIP

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

19.png
已邀请:

要回复问题请先登录注册