有 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的情况。
所以状态的划分和转移很重要,设计错了就很麻烦。