我有这个任务：
安娜妈妈打开了一包糖果，她想把它分发给孩子们作为奖励。这样他们就不会 他们之间会发生冲突，所以在比赛中获得更好名次的人当然不能少 比那些最终落得更糟糕的地方的糖果。安娜可以将 C 糖果分给 D 孩子有多少种方式？
任务：
对于给定的数字 D 和 C，找出糖果可能的分布数量。
入口：
文件的第一行有一个数字 Q 表示组数。
有 Q 行，其中有一对数字 D 和 C。
输出：
程序的输出是每个集合模 (2^30)-1 的结果，在单独的行上。
示例 输入：
3
1 10
2 4
3 8
输出：
1
3
10
我编写了这段代码并且它可以工作，但是当我有 1000 个输入时，我在评估器中得到 **Timelimit **，你能帮助我编写运行速度更快的代码吗？
def generate_combinations(d, c, current_combination=None, combinations=None):
if current_combination is None:
current_combination = []
if combinations is None:
combinations = []
if d == 0:
if c == 0:
if all(current_combination[i] <= current_combination[i + 1] for i in range(len(current_combination) - 1)):
combinations.append(list(current_combination))
return
for i in range(c + 1):
generate_combinations(d - 1, c - i, current_combination + [i], combinations)
return combinations
c = 8
d = 3
pocet = int(input())
for i in range(pocet):
d, c = map(int, input().split())
print(len(generate_combinations(d, c)))
我也有使用动态规划的版本
def dynamic_programming(d, c):
dp = [[0] * (c + 1) for _ in range(d + 1)]
dp[0][0] = 1
for i in range(1, d + 1):
for j in range(c + 1):
dp[i][j] = dp[i - 1][j]
if j >= i:
dp[i][j] += dp[i][j - i]
dp[i][j] %= (2 ** 30 - 1)
b = dp[d][c]
return dp[d][c]
q = int(input().strip())
for i in range(q):
d, c = map(int, input().split())
print(dynamic_programming(d, c))
为了更好地理解，这里举个例子，如果我们想将 8 颗糖果分给 3 个孩子，我们有 21 种可能性：
[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[0, 5, 3]
[0, 6, 2]
[0, 7, 1]
[0, 8, 0]
[1, 0, 7]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[1, 4, 3]
[1, 5, 2]
[1, 6, 1]
[1, 7, 0]
[2, 0, 6]
[2, 1, 5]
[2, 2, 4]
[2, 3, 3]
[2, 4, 2]
[2, 5, 1]
[2, 6, 0]
[3, 0, 5]
[3, 1, 4]
[3, 2, 3]
[3, 3, 2]
[3, 4, 1]
[3, 5, 0]
[4, 0, 4]
[4, 1, 3]
[4, 2, 2]
[4, 3, 1]
[4, 4, 0]
[5, 0, 3]
[5, 1, 2]
[5, 2, 1]
[5, 3, 0]
[6, 0, 2]
[6, 1, 1]
[6, 2, 0]
[7, 0, 1]
[7, 1, 0]
[8, 0, 0]
只有 10 种可能性适合这个任务：
[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[2, 2, 4]
[2, 3, 3]
如果您只想计算有效组合的数量，您可以使用此代码，将糖果分配给“最好”的孩子，然后递归地将糖果的余额分配给其他孩子：
def distribute_candies(C, Q, last_C = None):
valid = 0
if C == 0:
# can only distribute 0 as [0] * Q
return 1
if Q == 1:
# they get them all
return 1
# maximum number of candies the "best" person can have is C,
# or as many as the last person had if that is less
# minimum number (which still allows distribution) is (C + Q - 1) // Q
maxc = min(C, last_C if last_C else C)
minc = (C + Q - 1) // Q
for c in range(maxc, minc-1, -1):
valid += distribute_candies(C - c, Q - 1, c)
return valid
distribute_candies(4, 2)
# 3
distribute_candies(8, 3)
# 10
如果您对实际组合感兴趣，可以使用此代码（只需使用返回值的
lendef distribute_candies(C, Q, last_C = None):
if Q == 1:
# they get them all
return [[C]]
# maximum number of candies the "best" person can have is C,
# or as many as the last person had if that is less
# minimum number (which still allows distribution) is (C + Q - 1) // Q
maxc = min(C, last_C if last_C else C)
minc = (C + Q - 1) // Q
dist_C = []
for c in range(maxc, minc-1, -1):
dist_C += [l + [c] for l in distribute_candies(C - c, Q - 1, c)]
return dist_C
distribute_candies(4, 2)
# [[0, 4], [1, 3], [2, 2]]
distribute_candies(8, 3)
# [[0, 0, 8], [0, 1, 7], [0, 2, 6], [1, 1, 6], [0, 3, 5], [1, 2, 5], [0, 4, 4], [1, 3, 4], [2, 2, 4], [2, 3, 3]]