Number of Dice Rolls With Target Sum LeetCode solution in Python

1
# Runtime: 782 ms (Top 50.50%) | Memory: 18.9 MB (Top 42.22%)
2

3

4
class Solution(object):
5
    def numRollsToTarget(self, n, k, target):
6
        """
7
        :type n: int
8
        :type k: int
9
        :type target: int
10
        :rtype: int
11
        """
12

13
        mem = {}
14

15
        def dfs(i, currSum):
16

17
            if currSum > target:
18
                return 0
19

20
            if i == n:
21
                if currSum == target:
22
                    return 1
23
                return 0
24

25
            if (i, currSum) in mem:
26
                return mem[(i, currSum)]
27

28
            ans = 0
29
            for dicenumber in range(1, k + 1):
30
                ans += dfs(i + 1, currSum + dicenumber)
31

32
            mem[(i, currSum)] = ans
33

34
            return mem[(i, currSum)]
35

36
        return dfs(0, 0) % (10**9 + 7)