C语言动态规划(DP)入门的——-最长非降子连串(O(n^2))

首先糟写博客,我分享的凡本人正好上学的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

C语言, 

下边是代码(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 }