设为首页 加入收藏

TOP

动态规划(DP)入门之-------最长非降子序列(O(n^2))
2018-10-21 20:09:17 】 浏览:26
Tags:动态 规划 入门 ------- 最长 序列

第一次写博客,我分享的是我刚学习的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 }

 

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇实现解一元二次方程(循环) 下一篇C 语言 习题 1-14

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目