线性DP-最长上升子序列

Mingci / 2023-08-21 / 原文

概念

最长上升子序列是指一个序列中最长的单调递增的子序列，字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。
求最长上升子序列的长度可以用线性DP。

思路

1.读入数据，dp[i] 代表以第 i 个数为结尾的最长上升子序列的长度
2.大循环开始，从1到n，计算 dp[i]，初始化为1（特别重要）
3.小循环，从1到 i-1，如果 a[j] 小于 a[i] 的话，说明这个数可以和 dp[i] 组成上升子序列，状态转移方程是 dp[i]=max(f[i],f[j]+1)

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[2005],dp[100005];
int main(){
	cin >>n;
	for(int i = 1;i <= n;i++)cin >> a[i];
	for(int i = 1;i <= n;i++){
		dp[i]=1;//初始化一定一定要记得放在大循环里！不要在外面写了个dp[1]=1 !!
		for(int j = 1;j <= i-1;j++){
			if(a[j]<a[i]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	int ans = -100005;
	for(int i = 1;i <= n;i++)ans = max(ans,dp[i]);
	cout << ans;
	return 0;
}

~~就因为那个初始化放错了地方，原本满分变成了0~~，谨以此记，警示后人。