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比較大的話，容易逾時

介紹一種類似該問題的二分法解法：巨人排隊問題