一维DP

Tian

2025-10-08 15:46:18

发布于：广东

7阅读

0回复

0点赞

#include<iostream>
using namespace std;
int dp[1005],a[1005],n;
//dp[i] = j; 指到达 第 i 位 所纪录上升子序列的长度最大为 j
//找影响状态的原因 ，后者比前者大，记录就要 + 1
 /* dp[i], dp[j] (j<i) 
   if(a[j] < a[i]) 
   		dp[i] = dp[j]+1;
   else
   		dp[i] = dp[j];
	运用两个for解决可以
	 
   归纳：dp[i] = max(dp[j]+1,dp[i]);
*/
int main(){ 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i] = 1;//最开始的时候，最基础长度是为 1 
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j] < a[i] ){
				dp[i] = max(dp[j]+1,dp[i]);
			}
		}
//		cout<<dp[i]<<" ";
		ans = max(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}
//Tian

有帮助，赞一个

去预览

0/2000

全部评论 1

Tian

解释2

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], dp[N]; // 定义数组a和dp，用于存储输入的数列和最长上升子序列长度
//dp[i] = j; 当遍历到下标 i 时，获取到的最长上升子序列的长度为 j；
int n,ans; // 存储最终的最长上升子序列长度

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; 
		dp[i] = 1; // 初始时，最长上升子序列长度至少为1（自己本身）
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i]) {
				dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]，如果可以接在dp[j]后面
			}
			ans = max(ans, dp[i]); // 更新全局最长上升子序列长度
		}
	}
	cout << ans << endl;
	return 0;
}

2025-10-08 来自广东