动态规划——最长上升子序列问题两种角度及优化算法

最长上升子序列

一个数的序列 bi，当 b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列( a1, a2, ..., aN)，我们可以得到一些上升的子序列( ai1, ai2, ..., aiK)，这里1 <= i1< i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

Input

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

Output

最长上升子序列的长度。

Sample Input

7
1 7 3 5 9 4 8

Sample Output

解题思路：

找子问题 “求以ak（k=1, 2, 3…N）为终点的最长上升子序列的一个上升子序列中最右边的那个数，称为该子序列的长度” “终点”。

虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。

方法一：状态i的值dp[i] 由若干个值已知的状态值dp[0], dp[1], ..., dp[i-1]推出，复杂度O(n^2)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_N = 2000;
int a[MAX_N];
int dp[MAX_N];

int main(void) 
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		dp[i] = 1;
	}

	for (int i = 1; i < n; i++)
		for (int j = 0; j < i; j++)
			if(a[j] < a[i])
				dp[i] = max(dp[i], dp[j] + 1);

	cout << *max_element(dp, dp + n) << endl;

	return 0;
}

方法二：状态i的值dp[i]在被更新的时候, 依据dp[i]去更新和状态i相关的dp[i+1], ..., dp[n-1]的值复杂度O(n^2)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_N = 2000;
int a[MAX_N];
int dp[MAX_N];

int main(void) 
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		dp[i] = 1;
	}

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if(a[j] > a[i])
				dp[j] = max(dp[j], dp[i] + 1);

	cout << *max_element(dp, dp + n) << endl;

	return 0;
}

但这一算法还可以继续优化：将全部dp[i]的值初始化为INF。然后数组中除了INF之外为单调递增，所以每个dp[i]最多只需要一次更新。对于更新位置不必逐个遍历，可以利用二分搜索，这样复杂度可降为O(nlogn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_N = 2000;
const int INF = 9999999;
int a[MAX_N];
int dp[MAX_N];

int main(void) 
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	fill(dp, dp + n, INF);

	for (int i = 0; i < n; i++)
		*lower_bound(dp, dp + n, a[i]) = a[i];

	cout << lower_bound(dp, dp + n, INF) - dp << endl;

	return 0;
}