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]。
这样统计不重复也不遗漏
by 小粉兔 @ 2018-07-22 10:59:48
@[洛奇洛](/space/show?uid=92887)
$ f[i][j] $ 表示将前 $ i $ 个数分成 $ j $ 组的最值
$ f[i-1][j-1] $ 表示前 $i-1$ 个数分成了 $j-1$ 组,所以我们可以考虑将第 $i$ 个数单独分为一组,即第 $j$ 组,所以可以继承状态.
如果 $j$ 组中每个数都大于 $1$ ,那么我们可以让所有数都 $-1$ ,并把拿出来的数放在第 $j+1$ 组,所以可以从 $f[i-j][j]$ 继承状态.
表述的可能不是很好,请见谅
by nothingness @ 2018-07-22 11:04:27
嗯嗯,谢谢你
by 高二老年人 @ 2018-07-23 15:46:31
@[小粉兔](/space/show?uid=10703)
那么这道题的思想就是减少i的值,递推直到i=1对吗?
by 高二老年人 @ 2018-07-23 16:57:25
是的,这也是一般的DP/递推的核心思想
by 小粉兔 @ 2018-07-23 17:21:56
@[小粉兔](/space/show?uid=10703)
哦,谢谢dalao
by 高二老年人 @ 2018-07-23 17:23:31