【算法分析】

通过第i个元素的放置和前i个元素中的第k个元素的情况进行分类讨论，

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=30;
LL f[N]={0,0,1};
int main()
{
	int n;
	cin>>n;
	for(int i=3;i<=n;i++)
	{
		f[i]=(i-1)*(f[i-2]+f[i-1]);
		/*
		把第i个元素放在一个位置，一共有i-1种方法，比如放在位置k处。
		1.把编号为k的元素放到i处，那么剩下的i-2个元素就有f[i-2]种方案.
		2.把编号为k的元素不放到i处，那么就等于i-1个元素的错排，就有f[i-1]种方案 
		*/
	}
	cout<<f[n];
	return 0;
}