放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

n的m划分递推

挑战程序设计竞赛第二版.jpg

有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划分递推

评论 9

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    写的好清晰,看懂了.

    yoer777年前 (2017-03-15)回复
  2. #1

    看了2天了,一直不明白集合{ai}如何定义。求指点

    奥特曼9年前 (2015-02-12)回复
    • 好久以前的文章,我回忆了一下,{ai}是一系列非负整数的“集合”,允许元素相等,比如{0,1,1,2}

      hankcs9年前 (2015-02-12)回复
      • 为什么说 此时{ai}的个数等于{ai – 1}的个数,不知道为什么我完全找不到思路。

        奥特曼9年前 (2015-02-12)回复
        • 有x个确定不重复的集合,每个集合中每个小组都去掉一个元素,比如{1,2,3}=>{0,1,2},去掉了之后依然是确定不重复的。

          hankcs9年前 (2015-02-12)回复
          • 按原题来说,n=4,m=3;我是这样理解的集合ai的:a1={1,1,2},a2={1,3},a3={2,2},a4={4};这是4组n的m划分。那么ai=0是什么意思

            奥特曼9年前 (2015-02-13)
          • 上文说过{ai}里一共有m个数,那么0表示空的分组,是逻辑产物,比如1的3划分,dp[3 ][1 ] := {0,0,1},每个元素+1,得出你说的a1={1,1,2},a2至a4是dp[2 ][4 ],递推dp[3 ][4 ]=dp[3 ][1 ]+dp[2 ][4 ]。

            hankcs9年前 (2015-02-13)
          • 实际上,你的回复有错误,在此定义下a2={0,1,3},依次类推

            hankcs9年前 (2015-02-13)
          • 太谢谢了,困扰了我好几天了,现在终于有点思路,虽然不是100%,但感觉上懂了90%。还有10%说不出来的感觉,可能内功不足

            奥特曼9年前 (2015-02-13)

我的作品

HanLP自然语言处理包《自然语言处理入门》