n的m划分递推

有n个无区别的物品，将它们划分为不超过m组，求出划分方法数模M的余数。

限制条件：

1≤m≤n≤1000

2≤M≤10000

这样的划分被称作n的m划分，dp数组可以这么定义：

dp[i][j]=j的i划分的总数。

递推关系的难点在于不重复。我们采用一种标准将问题化为子问题，这个标准需要用到一种新的定义。我们定义n的m划分具体为一个集合{a_i}，{a_i}满足∑^m_i=1 a_i = n 。可以看出{a_i}里一共有m个数，这m个数不一定大于0。

这个标准是：是否存在某个a_i=0；这样可以将{a_i}分为两种情况：

1、不存在某个a_i=0

此时{a_i}的个数等于{a_i – 1}的个数，即 n – m 的 m 划分。理解起来并不难，集合里每个数都减去1，一共减了m个。

此时dp[i][j] = dp[i][j – i] 。

2、存在某个a_i=0

此时{a_i}的个数等于 n 的 m – 1 划分。可以这样思考，存在a_i=0，说明划分一定不足m组，那么至少可以少分一组同时满足划分数相同。

此时dp[i][j] = dp[i – 1][j] 。

那么{a_i}总的划分数就是这两种情况的综合，dp[i][j] = dp[i][j – i] + dp[i – 1][j]。

代码什么的就算了，码农级别的实现。这是《挑战程序设计竞赛(第2版)》动态规划里面的一个小问题，看的时候花了点时间想明白，记下来备用。

 知识共享署名-非商业性使用-相同方式共享：码农场 » n的m划分递推