给定一个数组a（可能包含相同的数），求它有多少个不同 ... - 日新月异的微博- 日新微博

给定一个数组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项构成的不同子序列的个数。初值：dp=1因为只有一个空子序列我们现在考虑dp（1）如果数列第i项在之前没有出现过，是一个新数显然dp=dp[i-1]*2这是因为前(i-1)项的子序列本身，以及添加上第i项，都是一个子序列，这是比较容易的情况。如果全是这样，人生就完美了……因为我们会推出dp=2^i，但还有讨厌的第二种情况。（2）如果第i项在之前出现过，假设j是它最近一次出现的

2021年07月13日 21时32分来自问答库 >> 计算机类

赞 | 举报 | 转发 | 收藏

评论共 0 条