交友问题 | 动态规划

描述

如果有n个人，每个人都可以保持单身或与其他人结成一对。每个人只能找一个对象。求总共有多少种保持单身或结对的方式。用动态规划求解。

输入

输入第一行t表示测试用例的数量

对于每一个测试用例, 输入一个整数n表示人数1<=n<=18

输出

针对每个测试用例，输出一个整数表示保持单身或结对的方式总数，末尾无换行

输入样例 1 

1
3

输出样例 1

4

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;ll t=0,n=0,i,j,sum=0;
ll dp[1001]={0};
/*
ll C(ll n,ll m){return (tgamma(n+1))/(tgamma(m+1)*tgamma(n-m+1));
}
*/
ll C(ll n ,ll m){int i,j;ll ans=1;for(i=n;i>n-m;i--){ans*=i;}for(i=1;i<=m;i++){ans/=i;}return ans;
}main(){//cout << C(0,0);cin >> t;while(t>0){cin >> n;for(i=0;i<=n;i++){if(i<=2){dp[i]=i;}else{dp[i]=dp[i-1]+(i-1)*dp[i-2];}}cout << dp[n] << "\n";t--;}
}