首页 > > 程序设计 > C/C++ >

动态规划（DP）入门之-------最长非降子序列(O(n…

2018-06-18 03:58:25来源：未知阅读 ()

第一次写博客，我分享的是我刚学习的DP问题也就是动态规划问题中的最长非降子序列。

问题描述：给你若干个数字或者自行输入几个数，输出其中最长非降子序列的长度。如5,3,4，8,6,7，最长子序列是3,4,67，所以最长非降子序列长度是：4.

面对这样一个问题，我们首先要定义一个“状态”来代表它的子问题，并且找到它的解。注意，大部分情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态（一种思考方法）。

假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度，其中i<N，那么上面的问题变成了原问题的一个子问题(问题规模变小了，你可以让i=1,2,3等来分析) 然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。OK，对照“入门”中的简单题，你应该可以估计到这个d(i)就是我们要找的状态。如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。状态找到了，下一步找出状态转移方程。

前1个数的LIS长度d(1)=1(序列：5)
前2个数的LIS长度d(2)=1(序列：3；3前面没有比3小的)
前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3，所以d(3)=d(2)+1)
前4个数的LIS长度d(4)=3(序列：3，4，8；8前面比它小的有3个数，所以 d(4)=max{d(1),d(2),d(3)}+1=3)

差不多可以找出来了d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]

下面是代码（C语言）：

 1 #include<stdio.h>
 2 #define Max 10
 3 int list (int A[],int n);
 4 int list (int A[],int n)//比较多个d[j]的大小关系，每次确定i再比较时（d[j]+1）和1的比较及d[i]的初始化问题
 5 {    int *d=(int*)malloc(sizeof(int)*n);//动态数组的创建，d为数组名
 6     int j,i;
 7     int len=1;//d[n]表示第n个元素之前的最长非降子序列
 8     for(i=0;i<n;++i)//i用来遍历数组中每一个元素
 9     {
10         d[i]=1;//每一个i都有一个确定的最长非降子序列，所以需要每次初始化d[i]
11         for(j=0;j<i;++j)//i已经确定为某一个值，此时需要遍历比较i和i之前的数(j)
12         {
13             if(A[j]<=A[i]&&d[j]+1>d[i])//i之前(即j)有多个数比i小时需要取其中最大的d[i]，类似于(a>max,max=a)
14                 d[i]=d[j]+1;
15         }
16         if(d[i]>len)len=d[i];//len取循环之后的最大值
17     }
18     free(d);
19     
20     return len;
21 }
22 int main(void)
23 
24 {
25 
26     int A[Max];
27     int i;
28     for(i=0;i<Max;i++)
29     {
30         scanf("%d",&A[i]);
31     }
32     printf("该数组的最长非降子序列长度是%d\n",list(A,10));
33     return 0;
34 }