algorithm - 将n个相同的球分配到组中以使每个组至少有k个球的方式有几种？

我试图用递归和记忆来实现这一点，我已经确定了以下基本情况。
i）当n==k时，只有一个组有所有的球。
ii）当k>n时，没有组可以有至少k个球，因此为零。
我不能从这里往前走。怎么能做到？
以n=6，k=2为例
（2、2、2）
（4,2）
（三、三）
（六）
即可以形成4个不同的分组。

最佳答案

这可以用下面描述的二维递归公式来表示：

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视为可能的最小球数，并将问题分为两种情况：是否有一个框中正好有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)时间内计算出。