aboutsummaryrefslogtreecommitdiffstats
path: root/1155/main.py
blob: c0af065a36ca083f103dfa4134bca66ade26a62d (plain) (blame)
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
#!/usr/bin/env python


from functools import lru_cache


class Solution:
    @lru_cache(None)
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        if d == 1:
            if 0 < target <= f:
                return 1
            return 0
        if target < d or target > f * d:
            return 0
        res = 0
        for i in range(1, f + 1):
            res += self.numRollsToTarget(d - 1, f, target - i) % (10**9 + 7)
        return res % (10**9 + 7)


def main():
    solution = Solution()
    print(solution.numRollsToTarget(1, 6, 3))
    print(solution.numRollsToTarget(2, 6, 7))
    print(solution.numRollsToTarget(2, 5, 10))
    print(solution.numRollsToTarget(30, 30, 500))


if __name__ == "__main__":
    main()