《最长非降子序列》 动态规划算法入门

题目描述

一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度

思路分析

编写代码

递归的代码看起啦更加好理解一些，不过用循环的方法代码更加简洁

使用递归的方法

show you code:

#include 
  
   
using namespace std;
int dp[6];

int max(int a,int b)
{
	return (a>b)  a:b;
}

int dp_fun(int *A,int i,int num)
{
	if(i == 0)
	{
		dp[i] = 1;
		return max(dp[i],dp_fun(A,i+1,num));
	}
	else
	{
		dp[i] = 1;
		for(int j=0;j
   
    dp[i]) dp[i] = dp[j]+1; } if(i == num) return dp[i]; else return max(dp[i],dp_fun(A,i+1,num)); } } int main(){ int A[] = { 5, 3, 4, 8, 6, 7 }; cout<
    
     
 






     
使用循环的方法
     
show you code:
     
 
     
#include 
      
       
using namespace std;

int lis(int A[], int n){
    int *d = new int[n];
    int len = 1;
    for(int i=0; i
       
        d[i]) d[i] = d[j] + 1; if(d[i]>len) len = d[i]; } delete[] d; return len; } int main(){ int A[] = { 5, 3, 4, 8, 6, 7 }; cout<