3027: 集合的划分题解（DP）

解题思路:递推公式- 将n - 1个子集放入k - 1个盒子， 如果第n个子集不在n- 1子集中， 那么方案数 f[n-1][k-1], 如果第n个子集在n-1个子集之中，那么方案数k * f[n-1][k]

注意事项: 返回类型long long

参考代码:

#include<iostream>
#include<limits> 
using namespace std;
const int N = 1e2 + 10;
long long dp[N][N];
//dp[i][j]i个元素放入j个空盒 
int main()
{
	int n,k;
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) {
		dp[i][1] = 1; 
		dp[i][i] = 1;
	}
	for(int i = 1; i <= n; i ++)
		for(int j = 2; j <= k; j ++)
			dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j];		
	
	cout << dp[n][k];
	return 0;
}