将 n 个相同的球分配到组中以使每组至少有 k 个球的方法有多少种？
Number of ways of distributing n identical balls into groups such that each group has atleast k balls?
我正在尝试使用带记忆的递归来做到这一点，我已经确定了以下基本情况。
I) 当n==k时只有一组有所有的球
II) 当 k>n 时，没有组至少有 k 个球，因此为零。
我无法从 here.How 前进，可以这样做吗？
以n=6,k=2为例
(2,2,2)
(4,2)
(3,3)
(6)
即可以组成4个不同的分组。
这个案例可以很简单地解决：
桶数
桶的最大数量b可以确定如下：
b = roundDown(n / k)
每个有效分配最多可以使用 b 个存储桶。
具有 x 个存储桶的分布数量
对于给定数量的桶，可以很简单地找到分布数量：
将 k 个球分配到每个桶中。找出将剩余球 (r = n - k * x) 分配到 x 个桶的方法数：
total_distributions(x) = bincoefficient(x , n - k * x)
编辑：如果顺序很重要，这只会起作用。既然不是问题，我们可以在这里使用一些技巧：
每个分布都可以映射到一个数字序列。例如：d = {d1 , d2 , ... , dx}。我们可以很容易地生成所有这些序列，从 "first" 序列 {r , 0 , ... , 0} 开始，然后从左向右移动 1。所以下一个序列看起来像这样：{r - 1 , 1 , ... , 0}。如果只生成匹配 d1 >= d2 >= ... >= dx 的序列，则不会生成重复项。这个约束可以很容易地用来稍微优化这个搜索：如果给出 da - 1 >= db + 1，我们只能将 1 从 da 移动到 db（使用 a = b - 1），因为否则违反数组排序的约束。要移动的 1 总是最右边可以移动的。另一种思考方式是将 r 视为一元数，然后将该字符串简单地分成组，这样每个组至少只要它是后继者。
countSequences(x)
sequence[]
sequence[0] = r
sequenceCount = 1
while true
int i = findRightmostMoveable(sequence)
if i == -1
return sequenceCount
sequence[i] -= 1
sequence[i + 1] -= 1
sequenceCount
findRightmostMoveable(sequence)
for i in [length(sequence) - 1 , 0)
if sequence[i - 1] > sequence[i] + 1
return i - 1
return -1
实际上 findRightmostMoveable 可以优化一点，如果我们看一下序列的结构转换（更准确地说是序列的两个元素之间的差异）。但老实说，我懒得进一步优化它。
拼凑
range(1 , roundDown(n / k)).map(b -> countSequences(b)).sum()
这可以用下面描述的二维递归公式表示：
T(0, k) = 1
T(n, k) = 0 n < k, n != 0
T(n, k) = T(n-k, k) + T(n, k + 1)
^ ^
There is a box with k balls, No box with k balls, advance to next k
put them
上面的T(n,k)是分配n个球的数量，使得每个盒子至少得到k个。
诀窍是将 k 视为尽可能少的球数，并将问题分为两种情况：它们并用 n-k 个球递归）或不递归（然后用 k+1 的最小值和相同数量的球递归）。
示例，计算您的示例：T(6,2)（6 个球，每盒最少 2 个）：
T(6,2) = T(4,2) + T(6,3)
T(4,2) = T(2,2) + T(4,3) = T(0,2) + T(2,3) + T(1,3) + T(4,4) =
= T(0,2) + T(2,3) + T(1,3) + T(0,4) + T(4,5) =
= 1 + 0 + 0 + 1 + 0
= 2
T(6,3) = T(3,3) + T(6,4) = T(0,3) + T(3,4) + T(2,4) + T(6,5)
= T(0,3) + T(3,4) + T(2,4) + T(1,5) + T(6,6) =
= T(0,3) + T(3,4) + T(2,4) + T(1,5) + T(0,6) + T(6,7) =
= 1 + 0 + 0 + 0 + 1 + 0
= 2
T(6,2) = T(4,2) + T(6,3) = 2 + 2 = 4
使用动态规划，可以在O(n^2)时间内计算出来。
我正在尝试使用带记忆的递归来做到这一点，我已经确定了以下基本情况。
I) 当n==k时只有一组有所有的球
II) 当 k>n 时，没有组至少有 k 个球，因此为零。
我无法从 here.How 前进，可以这样做吗？
以n=6,k=2为例 (2,2,2) (4,2) (3,3) (6)
即可以组成4个不同的分组。
这个案例可以很简单地解决：
桶数
桶的最大数量b可以确定如下：
b = roundDown(n / k)
每个有效分配最多可以使用 b 个存储桶。
具有 x 个存储桶的分布数量
对于给定数量的桶，可以很简单地找到分布数量：
将 k 个球分配到每个桶中。找出将剩余球 (r = n - k * x) 分配到 x 个桶的方法数：
total_distributions(x) = bincoefficient(x , n - k * x)
编辑：如果顺序很重要，这只会起作用。既然不是问题，我们可以在这里使用一些技巧：
每个分布都可以映射到一个数字序列。例如：d = {d1 , d2 , ... , dx}。我们可以很容易地生成所有这些序列，从 "first" 序列 {r , 0 , ... , 0} 开始，然后从左向右移动 1。所以下一个序列看起来像这样：{r - 1 , 1 , ... , 0}。如果只生成匹配 d1 >= d2 >= ... >= dx 的序列，则不会生成重复项。这个约束可以很容易地用来稍微优化这个搜索：如果给出 da - 1 >= db + 1，我们只能将 1 从 da 移动到 db（使用 a = b - 1），因为否则违反数组排序的约束。要移动的 1 总是最右边可以移动的。另一种思考方式是将 r 视为一元数，然后将该字符串简单地分成组，这样每个组至少只要它是后继者。
countSequences(x)
sequence[]
sequence[0] = r
sequenceCount = 1
while true
int i = findRightmostMoveable(sequence)
if i == -1
return sequenceCount
sequence[i] -= 1
sequence[i + 1] -= 1
sequenceCount
findRightmostMoveable(sequence)
for i in [length(sequence) - 1 , 0)
if sequence[i - 1] > sequence[i] + 1
return i - 1
return -1
实际上 findRightmostMoveable 可以优化一点，如果我们看一下序列的结构转换（更准确地说是序列的两个元素之间的差异）。但老实说，我懒得进一步优化它。
拼凑
range(1 , roundDown(n / k)).map(b -> countSequences(b)).sum()
这可以用下面描述的二维递归公式表示：
T(0, k) = 1
T(n, k) = 0 n < k, n != 0
T(n, k) = T(n-k, k) + T(n, k + 1)
^ ^
There is a box with k balls, No box with k balls, advance to next k
put them
上面的T(n,k)是分配n个球的数量，使得每个盒子至少得到k个。
诀窍是将 k 视为尽可能少的球数，并将问题分为两种情况：它们并用 n-k 个球递归）或不递归（然后用 k+1 的最小值和相同数量的球递归）。
示例，计算您的示例：T(6,2)（6 个球，每盒最少 2 个）：
T(6,2) = T(4,2) + T(6,3)
T(4,2) = T(2,2) + T(4,3) = T(0,2) + T(2,3) + T(1,3) + T(4,4) =
= T(0,2) + T(2,3) + T(1,3) + T(0,4) + T(4,5) =
= 1 + 0 + 0 + 1 + 0
= 2
T(6,3) = T(3,3) + T(6,4) = T(0,3) + T(3,4) + T(2,4) + T(6,5)
= T(0,3) + T(3,4) + T(2,4) + T(1,5) + T(6,6) =
= T(0,3) + T(3,4) + T(2,4) + T(1,5) + T(0,6) + T(6,7) =
= 1 + 0 + 0 + 0 + 1 + 0
= 2
T(6,2) = T(4,2) + T(6,3) = 2 + 2 = 4
使用动态规划，可以在O(n^2)时间内计算出来。