一本通-1315：【例4.5】集合的划分（计数DP或递归）

【题目描述】 设S是一个具有n个元素的集合，S＝〈a1，a2，……，an〉，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk且满足： 1．Si≠∅ 2．Si∩Sj＝∅ (1≤i，j≤k，i≠j) 3．S1∪S2∪S3∪…∪Sk＝S

则称S1，S2，……，Sk是集合S的一个划分。

它相当于把S集合中的n个元素a1，a2，……，an放入k个(0＜k≤n＜30)无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。

【输入】 给出n和k。

【输出】 n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。

【输入样例】 10 6

【输出样例】 22827

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstdio>

using namespace std;

int n = 100005, k = 35;
vector<vector<long long> > d(n, vector<long long>(k));

int solve()
{
    if (k == 0) return 0;
    if (k == 1) return 1;

    for (int i = 1; i <= n; ++i) d[i][1] = 1;
    for (int i = 1; i <= k; ++i) d[i][i] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= k; ++j) {
            if (i > j) {
                d[i][j] = d[i - 1][j - 1] + j * d[i - 1][j];
            }
        }
    }
    return d[n][k];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    cout << solve() << endl;

    return 0;
}

这个程序在最后一个测试用例过不去。因为可能在n很大但是k接近n / 2的时候出现溢出，而使用递归并不会出现类似的问题，另外，动态规划并没有比递归性能强，因为也不存在重复计算的可能性。

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

long long solve(int n, int k)
{
    if (n < k || k == 0) return 0;
    if (k == 1 || n == k) return 1;
    return k * solve(n - 1, k) + solve(n - 1, k - 1);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;    
    cin >> n >> k;
    cout << solve(n, k) << endl;

    return 0;
}

思路是前n-1个放入k个盒子，最后一个从k个盒子里选一个放进去，或者是前n-1个放入k个盒子，最后一个放入单独的盒子里面。