文章目录

1. 1. 题目
2. 2. 分析

题目

---

子序列的定义：对于一个序列a=a[1],a[2],……a[n]，则非空序列a’=a[p1],a[p2]……a[pm]为a的一个子序列,其中1<=p1<p2<…..<pm<=n。 例如：4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。

• 对于给出序列a，有些子序列可能是相同的，这里只算做1个。
• 要求输出a的不同子序列的数量。

分析

---

直接分析好像比较麻烦，考虑的情况太多，故转向动态规划，进行step判决，以dp[i-1]表示a[0]…a[i-1]的子序列个数，添加一个树a[i]，需要考虑的情况如下
1、a[i]在之前没出现过，则a[i]自身成为一个子序列+1，其次之前的每一个子序列与a[i]组合可以构成新的子序列，同时还需要包括之前的子序列，故+2dp[i-1]，导出有如下递推关系
d[i] = 2d[i-1]+1
2、如果a[i]在之前出现过，则需要进行相应的扣除，首先自身成为的子序列需要扣除，则-1，同时上一次出现位置，所导致的增加的子序列需要扣除，则dp[上一次出现的位置-1]
d[i] = 2d[i-1]+1-1-d[上一次出现位置-1]
根据上述两个公式即可，当然在编程的时候需要注意一些细节，如上一次出现的位置在0处需要特别考虑。编程时，初始化条件

dp[0] = 1;
index[a[0]] = 0;

完整代码下载见github-eesly

//获取子序列数
int subNum(int a[],int n)
{
	//记录下标表示是否出现过，简单的hash
	int *index = new int[n];
	memset((int*)index,-1,n*sizeof(int));
	int *dp = new int[n];
	memset((int*)dp,0,n*sizeof(int));
	dp[0] = 1;
	index[a[0]] = 0;
	for (int i = 1; i<n; i++)
	{
		//如果前面没有相同的,则a[i]自身成为一个子序列，故+1
		//还包括之前的子序列+dp[i-1]
		//还包括之前的子序列和a[i]构成新的子序列+dp[i-1],故总共有d[i-1]*2+1
		if (index[a[i]] == -1)
			dp[i] = dp[i-1]*2+1;
		//如果前面已有相同的，首先假定与前面不同获得d[i-1]*2+1个子序列，然后再扣除
			//情况1：和第一个数相同故只需要-1即可
		else if(index[a[i]] == 0)
			dp[i] = dp[i-1]*2+1 -1;
			//情况2：和后面数相同，则首先a[i]自身构成的子序列已经重复，需-1
			//同时，前一个位置的与a[i]相同的数位置，由于增加了该数所增加的全部子序列数需要扣除-dp[index[a[i]]-1]即可
		else
			dp[i] = dp[i-1]*2+1 -1 - dp[index[a[i]]-1];
		index[a[i]]=i;	
		//根据上述推导，可以发现如果对每个子序列进行操作会是一个O(2^n)级的复杂度
	}
	return dp[n-1];
}