我正在努力寻找如何将90个苹果放入90个盒子的全部可能性。任何数量的苹果都可以放在一个盒子里(0到90个苹果(，但所有的苹果都必须放在盒子里。我使用了递归，但完成计算花了太多时间。我只能用少量的苹果和盒子来测试我的代码。有人能帮我降低代码的时间复杂性吗？提前谢谢。
import math
boxes = 3
apples = 3
def possibilities(apples, boxes):
if apples == 0:
return 1
if boxes == 0:
return 0
start_point = 0 if boxes > 1 else math.floor(apples/boxes)
p = 0
for n in range(start_point, apples+1):
p += possibilities(apples-n, boxes-1)
return p
t = possibilities(apples,boxes)
print(t)
在我看来，问题在于找到最大90个元素的排序列表的数量，这些元素的和等于90。
有一个概念与此非常接近，我们称之为数的分区。
例如，4的分区是[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]。
经过一番研究，我发现这篇文章与你的问题有关。
如中所述，递归方法会导致对大数字进行很长的计算，但
一种更有效的方法是通过一种称为动态编程的方法。这里我们计算一个函数psum(n，k(，它是具有最大分量k或更小分量的n个部分的总数。在任何给定的阶段，我们都将计算出psum(1，k(、psum(2，k(，psum(3，k(…的值。。。，psum(n，k(对于一些固定的k。给定这个n值的向量，我们计算k+1的值如下：
psum(i，k+1(=psum(i，k(+p(i，k(对于的任何值
但回想一下，p(i，k(=∑j p(i-k，j(=psum(i-k(
因此，psum(i，k+1(=psum(i，k(+psum(i-k，k(
因此，只要稍微小心，我们就可以重用值的向量，并计算滚动值中psum(i，k(的值，以获得连续更大的k值。最后，我们有一个向量，其值为psum(i，n(。值psum(n，n(是所需的值p(n(。作为一个额外的好处，我们看到我们同时计算了p(1(，p(2(，…的值。。。，p(n(。
基本上，如果你把中间值放在一个列表中，并使用文章中给出的递归，
psum(i,k+1) = psum(i,k) + psum(i-k,k)
您可以使用以下功能：
def partitionp(n):
partpsum = [1] * (n + 1)
for i in range(2, n + 1):
for j in range(i, n + 1):
partpsum[j] += partpsum[j - i]
return partpsum[n]
在外部for循环的每次迭代中，列表partpsum包含所有值psum(1，k(、psum(2，k(，psum(3，k(。。。，psum(n，k(。在迭代结束时，您只需要返回psum(n，n(。