动态规划--子序列的个数

 

题目详情： 子序列的定义：对于一个序列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；

 

　　2、假设a[k] 与前面的k - 1个数其中一个相等，那依旧加上前k - 1个子序列个数 d(k - 1)，但是由于前面有与a[k]相等的数，所以要减掉重复的部分，如何找到重复的部分呢，假设离k最近的一个与a[k]相等的数为第t个a[t] = a[k]，即序列(a[1], a[2], ……,a[t],……,a[k - 1],a[k])，a[t] = a[k]；我们已经知道序列(a[1], a[2], ……,a[t])的序列个数为d(t)，那么d(t - 1)就是重复的部分，这里需要自己做好思考，也是算法的关键部分，这里我要解释的地方是，为什么只需要找到离k最近的t使得a[t] = a[k]？给出的解释是：我们是从1 - n对数组进行遍历的，计算d(i)的i就是从1到n依次计算的，那么第一次遇到a[k] = a[t]的情况满足条件：有且仅有一个t使得a[t] = a[k]，比如序列(1, 2, 3, 2, 4, 2)，分别计算d(1),d(2),d(3),d(4),d(5),d(6)；我们在计算d(4)的时候发现a[4] = a[2]（假设下标从1开始），所以d(4) = 2*d(3) - d(2 -1) = 2d(3) - d(1)；当计算d(6)的时候也有a[6] = a[4] = a[2]，但是由于我们前面已经把a[2]重复的部分减掉了，所以不需要再减，d(6) = 2 * d(5) - d(4 - 1) = 2d(5) - d(3).

 

　　过程繁琐，我总结一下结论：

 

　　状态转移方程为：

 

　　　　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 1000000007  
int 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)  
{  
    //int a[5] = {1, 2, 2, 3 ,3};  
    int a[4] = {1, 2, 3 , 2};  
    printf("the result is %d\n", run(a, 4));  
    return 0;  
}  

 

补充：软件开发 , C++ ,