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