第一次写博客，我分享的是我刚学习的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("该数组的最长非降子序列长度是%dn",list(A,10)); 33 return 0; 34 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
