AcWing 895. 暴搜,理解递归最长上升子序列
原题链接
简单
作者:
咸鱼堆上的猫
,
2024-04-10 12:56:10
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
using namespace std;
const int N=100000010;
int a[N],n;
int count;
int dfs(int a[],int i){
if(i==n){
cout<<i<<endl;
return 1;
}
int maxlen=1;
cout<<"进入加1"<<endl;
for(int j=i+1;j<=n;j++){
if(a[i]<a[j])
{
cout<<"前j: "<<j<<" "<<"maxlen: "<<maxlen<<endl;
maxlen=max(maxlen,dfs(a,j)+1); //可以用maxlen=dfs(a,j)调试递归,来理解递归
cout<<"后j: "<<j<<" "<<"maxlen: "<<maxlen<<endl;
}
}
cout<<"return maxlen: "<<maxlen<<endl;
return maxlen;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int max = dfs(a,1);
for(int i=2;i<=n;i++){
if(dfs(a,i)>max)
max=dfs(a,i);
}
cout<<max;
}
//记忆化 过
#include<bits/stdc++.h>
using namespace std;
const int N=100000010;
int a[N],n,m[N],res;
int dfs(int a[],int i){
if(m[i]) return m[i];
if(i==n){
return 1;
}
int maxlen=1;
for(int j=i+1;j<=n;j++){
if(a[i]<a[j])
{
maxlen=max(maxlen,dfs(a,j)+1);//可以用maxlen=dfs(a,j)调试递归,来理解递归
res = maxlen;
m[i]=res;
}
}
return maxlen;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int max = dfs(a,1);
for(int i=2;i<=n;i++){
if(dfs(a,i)>max)
max=dfs(a,i);
}
cout<<max;
}