子序列的个数
题目详情： 子序列的定义：对于一个序列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的不同子序列的数量。
输入： 长度为n的数组1<=n<=100,数组元素0<=a[i]<=110
输出：子序列 的个数对1000000007取余数的结果（由于答案比较大，输出Mod 1000000007的结果即可）。
函数头部： C/C++: int run(cons int *a,int n); java public static int run(int [] a);
这道题目也是困扰了我很久，一直找不到比较好的方法，这道题目应该是可以用动态规划做出来的，因此我也特地去学习动态规划的思想，并找了一些练习题做，可是这个状态转移方程着实难住我了，本来数学基础一般般，这就更加大了难度。虽然我最终解决了这道题目，可是那是建立在大神指点的情况下做出来的，我在这里只是把题解写出来，顺便裨补阙漏，看看自己的理解是否正确，其实，想和做是两回事，这里也请大家给与指正。
题解：
假设子序列的前k个数的子序列个数为d(k)，那么前k – 1个子序列的个数就为d(k – 1)个子序列，从k – 1 到k的变化是怎样的呢？
1、假设数组a[N]第k个数为a[k]，如果a[k] 与前面的k – 1个数都不相同，那么就有 : d(k) = d(k – 1) + 【d(k – 1) + 1】 =2d(k – 1) + 1，为什么呢？可以这样想，对于前k- 1项的子序列个数为d(k – 1)，那前k个数，无非就是在前k – 1项的基础上多加了一个数a[k]（a[k]与前k – 1个数任意一个都相等），那就在原来的组合上加上a[k]，就有d(k – 1)个，还有一个a[k]自己构成一个子序列，所以还要加1；
过程繁琐，，我总结一下结论：
状态转移方程为：
d(k) = 2 * d(k – 1) + 1; a[k] != a[i]，i = 1,2,3……k – 1;
d(k) = 2 * d(k – 1) – d(t – 1); 从k往前搜索，存在离k最近的t，使得a[t] = a[k].
状态转移方程分析出来的话，剩下的基本就是小菜一碟了，代码如下：
/*以下是题目详情： 子序列的定义：对于一个序列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的不同子序列的数量。 输入： 长度为n的数组1<=n<=100,数组元素0<=a[i]<=110输出：子序列 的个数对1000000007取余数的结果（由于答案比较大，输出Mod 1000000007的结果即可）。函数头部： C/C++: int run(cons int *a,int n); java public static int run(int [] a);*/#include <stdio.h>#include <stdlib.h>#define M 1000000007int run(const int *a,int n){long long SubArray[120] = {0};int LastIndex[120] = {0};int iter = 0;for(iter = 1; iter <= n; iter++){switch(LastIndex[a[iter – 1]]){case 0:{SubArray[iter] = (2 * SubArray[iter – 1] + 1) % M;break;}default:{SubArray[iter] = (2 * SubArray[iter – 1] – SubArray[LastIndex[a[iter – 1]] – 1] + M) % M;break;}}LastIndex[a[iter – 1]] = iter;}return SubArray[n] % M;}int main(void){a[4] = {1, 2, 3 , 2};printf(, run(a, 4));return 0;}
View Code
才能做到人在旅途，感悟人生，享受人生。
