这可以用下面描述的二维递归公式来表示:
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)
时间内计算。