放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理。另外,不要叫我楼主,谢谢。

n的m划分递推

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

限制条件:

1≤m≤n≤1000

2≤M≤10000

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

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

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

这个标准是:是否存在某个ai=0;这样可以将{ai}分为两种情况:

1、不存在某个ai=0

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

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

2、存在某个ai=0

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

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

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

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


转载须注明:码农场 » n的m划分递推

分享到:更多 ()

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机