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} ,且满足当i > j时，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 ",DPLIS(Arr, n)); return 0; }