-
Notifications
You must be signed in to change notification settings - Fork 85
/
272.py
31 lines (22 loc) · 748 Bytes
/
272.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
Problem:
Write a function, throw_dice(N, faces, total), that determines how many ways it is
possible to throw N dice with some number of faces each to get a specific total.
For example, throw_dice(3, 6, 7) should equal 15.
"""
def throw_dice(N: int, faces: int, total: int, accumulator: int = 0) -> int:
if N == 0 and total == 0:
return accumulator + 1
elif total < 0:
return accumulator
# dfs to calculate the answer
for i in range(1, faces + 1):
accumulator = throw_dice(N - 1, faces, total - i, accumulator)
return accumulator
if __name__ == "__main__":
print(throw_dice(3, 6, 7))
"""
SPECS:
TIME COMPLEXITY: O(faces ^ log(total))
SPACE COMPLEXITY: O(total) [call stack included]
"""