数划分

有 n 个无区别的物品,将他们划分成不超过 m 组,求划分方法数。

这个应该也算是一个入门级的 DP 题,但是对于初学的我来说状态还是不是很好想到。
开始我想嘛,这个简单嘛

f[i][j] 表示数字 i 的 j 的划分
f[i][j] = sum(f[i - k][j - 1]) k = 0..i

想的很简单,就是我把数字 k 作为一份,把剩下的 i - k 分为 j - 1 份,感觉对的哒!
不过问题来了,
比如 1+1+2和1+2+1这种就算重复了,我们这个关系不对,会多算。

后来看了这么做之后也想了好久,
我们可以这样划分状态:

f[i][j] 表示数字 i 的不超过 j 的划分有多少个
f[i][j] = f[i - j][j] + f[i][j - 1]

很莫名其妙的一个递推式,我看了好久(智商低就这样,没办法T_T)
是这样来的,首先我们考虑有 j 个划分!
那么

a1+a2+..+aj == i

那么如果把每个都减一的话就正好是 f[i-j][j] 的划分个数,我们可以由f[i-j][j]得到i正好有j个划分的情况。
如果其中有ai为0,那么其划分为 f[i][j-1],因为有一个数为0,就最多有j-1个划分啦,我们的状态是f[i][j]不超过j的划分,所以f[i][j-1]就包含了所有有ai为0的情况。

所以状态的划分和转移很重要,设计错了就很麻烦。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,357评论 0 33
  • 初时知道小山是因着容若,彼时痴迷于纳兰少爷的我,乍闻“纳兰是清代晏小山”这一说法,于是便疯狂地搜集所有关于小山的资...
    刘皮皮有点皮阅读 4,379评论 10 22
  • 我会做绿豆汤了。 以前觉得就是打个秋千的吊椅,现在也能让我装个文艺。 配着景,文学渣渣又想写点东西了。 哎你说,什...
    胡划拉阅读 1,526评论 2 2
  • swift基础小结 for 循环OC与Swift对比 While循环与downhill循环 OC与swift使用的...
    罗小耳阅读 1,950评论 0 0
  • 昨天下午单位停电了,老板说:没电也干不成活,都回家吧!我们三个欢呼雀跃!平时三个人轮流休息,没有同时休息过,终于一...
    新雅遇见读书阅读 1,648评论 1 1

友情链接更多精彩内容