#每日一面BAT#第19题 子序列的个数


给定一个数组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} 等。
已邀请:

cpcs - 诚实努力

赞同来自:


答案:
这个题本身不难,但是分析清楚不容易。
我们首先假设子序列可以为空——最后减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因为我们考虑了空的子序列。
还有一种分析可以不考虑空的子序列,也是类似的。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~