洛谷 P1595 信封问题 C语言递归

题目描述

某人写了 n 封信和 n 个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

输入格式

一个信封数 n，保证 n≤20。

输出格式

一个整数，代表有多少种情况。

输入输出样例

输入 #1

2
输出 #1

1
输入 #2

3
输出 #2

2
说明/提示
对于 100% 的数据，1≤n≤20。

代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
ll dfs(ll n)
{if(n == 0)return 1;if(n == 1)return 0;return (n-1)*(dfs(n-1)+dfs(n-2));
}
int main()
{ll n;cin >> n;cout << dfs(n);return 0;}