关于P1025状态转移方程思路的分析
状态转移方程为f[i][j] = f[i-1][j-1] + f[i-j][j]
思路
f[i][j] 表示 数i 分成j 份的方案数
最后输出f[n][k]即可
那么考虑 i 分成 j 份的一种方案。
因为同样的方案不算两遍，所以考虑这两种不同的方案：
① 方案中含有 1 的
② 方案中不含 1 的
显然这两种方案没有交集，并且相加就是 f[i][j]。
对于第①种，把一个 1 拿走，得到 f[i-1][j-1]
对于第②种，把每个数减 1，得到 f[i-j][j]。
这样统计不重复也不遗漏
f[i-1][j-1] 和 f[[i-j][j] 是怎么来的
f[i][j] 表示将前 i 个数分成 j 组的最值 f[i-1][j-1] f[i−1][j−1] 表示前 i-1 个数分成了j−1 组,所以我们可以考虑将第 i 个数单独分为一组,即第 j 组,所以可以继承状态.
如果 j 组中每个数都大于 1 ,那么我们可以让所有数都 −1 ,并把拿出来的数放在第 j+1 组,所以可以从 f[i-j][j] 继承状态.