欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

学习之动态规划

程序员文章站 2022-03-14 09:47:35
...

求最长子序列长度

问题描述:

上升序列(b1,b2,…,bn),当b1<b2<…<bn时,序列是上升的。给定一个序列(a1,a2,…an),可得到一些上升子序列(ai1,ai2,…aik),这里1<=i1<i2<…<ik<=n。一个序列,如(1,7,3,5,2,8),上升子序列有(1,3,5,8),(1,7,8)等等。子序列中最长的长度是4。设计算法求出一个数列的最长上升子序列长度。

输入:

第一行,输入数的个数,以下一行输入各个数。

输出:

最长子序列长度。

设备:

VC6.0或其他c语言编程软件

动态规划思路:
(1)将问题分成N个子问题(长度为N的序列)。
(2)以每个N为终点,判断子问题上升序列的长度。
(3)最后取最长上升子序列长度,得到整个问题的解。

具体方法(关键部分):
(1)数组从下标1开始存储。
(2)第一个上升子序列长度为1。 以后每一个考察两点:

  1. 上升子序列中,保证终点向左的每个数都小于终点N
  2. 在1.的前提下(b[a]>b[j]),记录子序列最大长度

(3)tmp在第二重循环前初置为0。记录最长长度。
(4)最后输出

代码:

#include<iostream>
#include<cstdio>
using namespace std; 
#define MAXV 1000
int b[MAXV+10];
int maxLen[MAXV+10];
int main()
{
  int N;	
  scanf("%d",&N);	
  for(int i=1;i<=N;i++)		
      scanf("%d",&b[i]);	
  maxLen[1]=1;	
  for(int a=2;a<=N;a++)	
  {		
    int temp=0;		
    for(int j=1;j<i;j++)		
    {			
       if(b[a]>b[j])			
       {				
           if(temp<maxLen[j])					
           temp=maxLen[j];			
       }		
    }		
    maxLen[a]=temp+1;	
  }	
 int maxL=-1;	
 for(int c=1;c<=N;c++)		
    if(maxL<maxLen[c])			
       maxL=maxLen[c];	
  printf("%d\n",maxL);	
  return 0
}

执行结果:

学习之动态规划

相关标签: 程序设计实习