1080: 最长上升子序列Ⅰ

题目描述

PIPI要来考考大家一个经典问题——最长上升子序列。

给你一个整数序列，包含n个整数，要你求最长上升子序列的长度~

输入

多组输入

第一行为一个整数n，1<=n<=1000

第二行包括n个整数，每个整数均在int范围内

输出

输出一个整数，表示最长上升子序列的长度。

样例输入

5

1 2 5 4 7

样例输出

4

思想：动态规划

这道题应该是严格上升，不包含等于。动态规划问题，实际上是一个填表的过程，第一要确定边界即初始化表格上的一些数据，以便于我们进行填表操作；第二要根据实际问题来确定状态转移方程，这是我们进行填表的规则，最后得到的dp表格就是我们要的结果。

注：第一行代表元素下标，第二行代表从第一个数到该元素最长上升子序列的长度

数组下标从1开始，默认dp[0]=0（这里不需要关注），边界dp[i] = 1初始化表格如下：

1	2	3	4	5
1	1	1	1	1

状态转移方程dp[i] = max(dp[i],dp[j]+1)更新表格：

1	2	3	4	5
1	2	3	3	4

取一个ans更新长度的最大值

填表过程可参考01背包问题，二维dp[i][j]数组填表，加深理解

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e3+5;
int dp[maxn];

int main(){
	int n;
	while(~scanf("%d",&n)){
		int a[n+1];
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		int ans = -1;
		// n ^ 2解法 
		for(int i=1;i<=n;i++){
			dp[i] = 1;	//边界初始条件，先假设每个元素自成一个子序列 
			for(int j=1;j<i;j++){	//查找i前面最大的长度dp[j] 
				if(a[i]>a[j]){
					dp[i] = max(dp[i],dp[j]+1);	//状态转移方程，用以更新dp[i] 
				}
			}
			ans = max(ans,dp[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
} 
           

此处是 n ^ 2解法 ，如果n比较大的话，容易超时

介绍一种类似该问题的二分法解法：巨人排队问题