动态规划---LIS

LIS--最长非降子序列

(讲DP基本都会讲到的一个问题LIS：longest increasing subsequence)

题目详情：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。

举个实际的例子来说，对于这个序列：5，3，4，8，6，7，求出其最长非降子序列的长度。

根据动态规划的基本思想，分析问题的状态及其状态转移方程，假设d(i) = j，i表示取序列的前i个数，j表示这前i个数字的最长非降序列的长度，首先我们来对前面几个数作分析：d(1) = 1，这个毋庸置疑的，前一个数的LIS就是1，当i = 2时，看到前两个数是（5, 3）由于3比5要小，所以d(2) = 1;当i = 3时，序列为(5, 3, 4)，4比3要大，比5要小，这个时候这个序列的子序列最大的显然为2，所以d(3) = 2；当i = 4时，序列为(5, 3, 4, 8)，8比前三个数都要大，但是要取出最长的非降子序列应该是(3, 4, 8)而不是(5, 8),分析到这里，就知道，在构造状态转移方程的时候，等式右边应该是一个比较结果的最大值，那又是哪些的比较结果呢？动态规划一般是要利用前面所得到的结果，这样才不会产生重复计算的问题，减少运算量。因此，参加“比较”的应该就是前面计算的到的结果进行比较，最后我们得到状态转移方程为

　　　　d(i) = max{ 1, d(j)+1} ,且满足A[i] >= A[j] (注：对于任意的i，都有d[i] >= 1)

　　我们来分析一下这个方程，max显然是为了找到最长的非降子序列，容易理解，在max里面加入1作为比较的一员，是因为，最坏的情况就是序列是单调递减的，那么每个数都是一个最长非降子序列，一个数的长度当然为1；那d[j]为什么要加1呢，因为你比较的数A[i] > A[j]，那么A[i]就是最长子序列的一员，所以直接在d[j]上加1，分析完毕。

　　得到了状态转移方程，惯例就是通过代码来实现它。

/* 
    动态规划 
    PRO: 一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。 
       (讲DP基本都会讲到的一个问题LIS：longest increasing subsequence) 
*/  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
int DPLIS(int Arr[], int n)  
{  
    int iterx = 0, itery = 0;  
    int maxVal = 0;  
    int *d = (int *)malloc(sizeof(int) * n);  
    memset(d, 0, sizeof(int) * n);  
    for(iterx = 0; iterx < n; iterx++ )  
    {  
        d[iterx] = 1;  
        for(itery = 0; itery < iterx; itery++)  
        {  
            if(Arr[iterx] >= Arr[itery])  
            {  
                d[iterx] = d[iterx] > d[itery] + 1 ? d[iterx] : d[itery] + 1;  
            }  
        }  
        if(maxVal < d[iterx])  
        {  
            maxVal = d[iterx];  
        }  
    }  
    free(d);  
    return maxVal;  
}  
int main(void)  
{  
    int Arr[100] = {4, 5,3 ,3 ,3 ,3 ,6 ,5 ,1 ,2};  
    int n = 10;  
    //int i;  
//    for(i = 100; i > 0; i--)  
//    {  
//        Arr[100 - i] = i ;  
//    }  
    printf("the result is %d\n",DPLIS(Arr, n));  
    return 0;  
}

注：1.本文版权归作者和CSDN所有，转载请注明出处，侵权必究！

2.本博客与博客园上的博客为同一博客主：http://www.cnblogs.com/bestDavid/

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