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

题目

给定一个数组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.已知一个大小为n的整型数组，现求该数组的全部连续子数组的元素之和的最大值，最优算法的时间复杂度是()如：a[4]={2,-1,3,-4}，它的全部连续子数组为{2,-1,3,-4,[2,-1],[-1,3],[3,-4],[2,-1,3],[-1,3,-4],[2,-1,3,-4]}，它们的元素之和为{2,-1,3,-4,1,2,-1,4,-2,0}，其中的最大值为4。A.O(logN)B.O(N)C.O(N*logN)D.O(N^2)

2.给定一个整数数组 nums （[-2,1,-3,4,-1,2,1,-5,4]), 用动态规划算法找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

3.设A是n个不同的数排好序的数组，给定数L和U，L ＜ U，设计一个算法找到A中满足L ＜ x ＜ U的所有的数x。

4.阅读以下说明和C++ 程序，将应填入(n)处的字句写在对应栏内。[说明]试从含有n个int 型数的数组中删去若干个成分，使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。[C++ 程序]include＜stdio.h＞define N 100int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};int a [N];define n sizeofb/sizeofb[0]void main ( ){kit k,i,j;(1)(2)for (i=1;i＜n; i++ ){for ( j=k;(3); j--);(4); /*长为 j+1 的子序列的终元素存储在 a[j+1]*/if ((5)k++; /*最长不减子序列长 k 增1*/}printf ( "K = %d\n ",k );}

参考答案和解析
正确答案：

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

更多“给定一个数组a(可能包含相同的数),求它有多少个不同的子序列。例如a={1,2,1,3}子序列有{1}{2}{3}{ ”相关问题

  • 第1题：

    用rand（)产生一个包含1000个1-20之间的整数的数组data1, 计算其中包含多少个1，多少个2，多少个3.......,并显示结果。 注：程序开始使用rand（'state',0) 对rand函数初始化。


    5

  • 第2题：

    编写程序。 （1）定义一个Circle类，其中包含一个用于求圆面积的方法。（2）定义一个长度为10的Circle类数组，该数组中每个元素均为Circle类对象，即半径不同的具体的圆。（3）编写代码求该数组中所有圆的面积和。


    第一空： #

  • 第3题：

    在一个操纵子中有多少个顺反子？

    A．2

    B．1

    C．3

    D．是变量


    是变量

  • 第4题：

    3、此处规定二叉树中，左子节点与右子节点地位不同（即某个父节点只有一个子节点时，也要区分它是左子节点还是右子节点）。定义一个函数c（n)，为按照此方法，构建一个包含n个节点的，符合规则的树的方法数。 问c（1), c（2), c（3), c（4)的值。

    A．1，1，2，3

    B．1，1，2，4

    C．1，2，4，8

    D．1，2，5，14


    错误

  • 第5题：

    求给定序列的前n项和（1+1/2+1/3+……）


    x 1 (n)已经是25点长的序列。但在x 2 (n)尾部需补零使之成为长25点的序列。由于循环移位，x 2 (n)的10个非零值(都为1)始终在区间[0，24]内，与x 1 (n)的非零值(都为1)相重合。因此25点循环卷积y 1 (n)的值都等于10。如图5.20所示。 $x 1 (n)和x 2 (n)都需要在尾部补零使它们成为长34点的序列，这样，在区间[0，33]内，x 1 (n)的尾部从n=25到n=33有9个零取样值，而x 2 (n)的尾部从n=10到n=33有24个零取样值。计算34点循环卷积时，设x 1 (n)不动，而将x 2 (n)折叠并进行循环移位，那么，在移位为0时，x 2 (n)尾部的24个零值正好与x 1 (n)的除第1个外的其余24个非零值对应，而x 2 (n)的除第1个外的其余9个非零值(注意，由于折叠和循环移位，这9个非零值现在位于从n=25到n=33的范围内)正好与x 1 (n)尾部从n=25到n=33的9个零值对应。x 2 (n)的第1个非零值现在位于n=0处，与x 1 (n)的第1个非零值对应。随着移位的进行，在移位为n=0到n=8范围内，都是这种情况，不过，x 2 (n)的非零值与x 1 (n)的非零值重合的个数，每移位1次就增加1个，当n=9时，非零值重合的个数达到最大，即10个。此后，直到移位为24之前，都有10个非零值相重合。从n=25开始，随着移位增加，非零值重合的个数将逐个减少，一直到移位等于33，将只有1个非零值相重合。 其实，这个问题的解答非常简单，因为循环卷积的长度正好等于x 1 (n)与x 2 (n)线性卷积的长度，即25+10-1=34，因而循环卷积与线性卷积的结果相等，所以按照线性卷积的计算来思考，立即可以得出图5.21所示的结果。

相关内容