(讲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
#include
#include
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/