我有这个任务:
安娜妈妈打开了一包糖果，她想把糖果分发给她的子元素们作为奖励.从而使得它们不 他们之间的冲突，所以当然谁完成了一个更好的地方在竞争中不能少， 比在更糟糕的地方吃的更好安娜可以用多少种方法把C个糖果分给D个子元素？
任务:
对于给定的数字D和C，找出糖果的可能分布的数量.
入口:
在文件的第一行有一个数字Q，表示集合的数量.
有Q行，有一对数字D和C.
- 1个≤Q≤1000
- 1个≤D≤100
- 1个≤C≤5,000
输出:
程序的输出是每组模(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]