将n分成恰有k个部分的分拆,称为k部分拆数,记作p(n,k)。
- p(n−k, k)是将每个数都加1,从而对p(n, k)有贡献。(如 1 1 1 -> 2 2 2)
- p(n-1, k-1)是在开头增加一个数1,从而对p(n, k)有贡献。(如 1 1 -> 1 1 1,从而达到<=的转移效果)
- p(n−k, k−1)是将每个数都加1,并在开头增加一个数1,从而对p(n, k)有贡献。(如 2 3 -> 1 3 4,因为在增加数字1的同时,每个数都增加了1,保证了严格递增)
p(n, k) = p(n−1, k−1) + p(n−k, k) // <=p(n, k) = p(n−k, k−1) + p(n−k, k) // <