暑期解题报告之一

今天在codevs刷天梯，中途遇到一题，名曰“数的划分”，一开始认为是简单动规，结果久久不过，反复修改未果，最后看过题解。才发现了原来此中动规有深意，其中包含了一种组合数学的特殊数Stirling数。在看过大神的博客后，有一些理解，在此做一个解题报告，以防遗忘。

题意：

将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5

1 5 1

5 1 1
问有多少种不同的分法。

Stirling数：

S(n,m)是将n个数拆分成非空的m个部分的方案数

思路:

结合题意，可以定义出状态dp[i][j]，表示了针对前 i 件物品(每件即一个价值为1的数)放置在 j 个区间里的方案数。

则有状态转移方程：dp[i][j] = dp[i-j][j] + dp[i-1][j-1];

第一项表示将当前的第i个数加入到已有的j个集合中，第二项表示将第i个数作为单独的一个集合独立出来。