人工智能AI面试题-2.3 数组中⼦子序列列的个数

2.3 数组中⼦子序列列的个数 📊💡 1. 题⽬目描述 给定⼀个数组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}等。 2. 分析与解法 🕵️‍♂️🧩 这个题本⾝不难，但是分析清楚不容易。我们⾸先假设⼦序列可以为空，最后减1就好了。假设 dp[i]表⽰数列前i项构成的不同⼦序列的个数。初值dp[0] = 1，因为只有⼀个空⼦序列。我们现在考虑 dp[i]：如果数列第i项在之前没有出现过，是⼀个新数，显然 dp[i] = dp[i - 1] * 2。这是因为前(i-1)项的⼦序列本⾝，以及添加上第i项，都是⼀个⼦序列，这是⽐较容易的情况。如果全是这样，⼈⽣就完美了……因为我们会推出 dp[i] = 2 ^ i，但还有讨厌的第⼆种情况：如果第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因为我们考虑了空的⼦序列。还有⼀种分析可以不考虑空的⼦序列，也是类似的。