1155. Number of Dice Rolls With Target Sum | 1654

 1class Solution:
 2    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
 3        # n = 3, k = 6, target = 5
 4        # 1+1+3
 5        # 1+2+2
 6        # 1+3+1
 7        # 2+1+2
 8        # 2+2+1
 9        # 3+1+1
10
11        # n = 3, k = 6, target = 17
12        # 5+6+6
13        # 6+5+6
14        # 6+6+5
15
16        # the first die can range from
17        # max(target - k*(n-1), 1)
18        # min(target - 1*(n-1), k), both inclusive
19
20        # the second die
21        # max(target - k*(n-2) - sum(prev_dice), 1)
22        # min(target - 1*(n-2) - sum(prev_dice), k)
23
24        # the i-th die
25        # max(target - k*(n-i) - sum(prev_dice), 1)
26        # min(target - 1*(n-i) - sum(prev_dice), k)
27
28        # recursive? dp?
29        modulo = 10**9 + 7
30
31        def recursiveDice(i: int, sum_prev_dice: int, mod_ways: int) -> int:  # n dice, k sides, target is global
32            # base: last die to throw
33            if i == n:
34                assert sum_prev_dice + k >= target and sum_prev_dice < target
35                return 1  # there's only one way to bridge sum_prev_dice to target
36
37            lo = max(target - k * (n - i) - sum_prev_dice, 1)
38            hi = min(target - 1 * (n - i) - sum_prev_dice, k)
39
40            for j in range(lo, hi + 1):
41                mod_ways += recursiveDice(i + 1, sum_prev_dice + j, mod_ways)
42                mod_ways %= modulo
43
44            return mod_ways
45
46        result = recursiveDice(1, 0, 0)
47
48        return result

 1class Solution:
 2    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
 3        modulo = 10**9 + 7
 4
 5        @lru_cache(None)
 6        def recursiveDice(i: int, sum_prev_dice: int) -> int:  # n dice, k sides, target is global
 7            # base: last die to throw
 8            if i == n:
 9                # assert sum_prev_dice + k >= target and sum_prev_dice < target
10                if sum_prev_dice + k < target or sum_prev_dice >= target:
11                    return 0
12                return 1  # there's only one way to bridge sum_prev_dice to target
13
14            lo = max(target - k * (n - i) - sum_prev_dice, 1)
15            hi = min(target - 1 * (n - i) - sum_prev_dice, k)
16
17            mod_ways = 0
18            for j in range(lo, hi + 1):
19                mod_ways += recursiveDice(i + 1, sum_prev_dice + j)
20                mod_ways %= modulo
21
22            return mod_ways
23
24        result = recursiveDice(1, 0)
25
26        return result