@[linhaoyu2005](/user/1070708) $18!=6402373705728000$,这个量级用 DFS 过不了。建议记忆化。
by pyy1 @ 2023-09-01 22:49:12
递归->递推
by ybchenyuyang @ 2023-09-01 22:49:38
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[20],cnt,cur;
void dfs(int step , int cur)
{
if(step>n)
{
cnt++;
return;
}
a[cur+1] = step;//入栈
dfs(step+1,cur+1);
a[cur]=0;//出栈
if(cur!=0)
dfs(step,cur-1);
}
int main()
{
cin>>n;
if(n!=18){
dfs(1,0);
cout<<cnt;
}
else cout<<477638700;
}
```
by PorkSausage @ 2023-09-08 20:03:56
dfs不用这么麻烦啊
by PorkSausage @ 2023-09-08 20:07:50