Number of Dice Rolls with Target Sum
You have d dice, and each die has f faces numbered 1, 2, ..., f.
Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.
Input: d = 1, f = 6, target = 3
Output: 1
Explanation:
You throw one die with 6 faces. There is only one way to get a sum of 3.From here.
Let's start off by examining it with 1 dice.
If we have 1 dice, and our target 1 <= N <= 6 then we will only ever have 1 way.
Now, what if we introduce 2 die?
Because a dice can only be rolled once, we'd want to use something multi-diimensional such as:
[ [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6] ]We've actually seen something like this before. When we have 2 dice with 6 faces and a target 12 that means that if we know the value of dice1, we can work out the value for dice2:
Target is 12
Dice1 is 6
Dice2 must be 6.
Now, let's go one step further. Let's see X number of die.
Our target value is 18. We have X die. Each die has 6 faces.
Assume we define our function as dp(num_dice, num_faces, target_value).
We will roll one dice and see how it changes things.
Die = 1. The remaining X dice must sum to 18 - 1 = 17 ways. This can happen with
dp(x, 6, 17).Die = 2. The remaining dice must sum to 18 - 2 = 16 ways. This can happen
dp(x, 6, 16)ways.Die = 3. The remaining dice must sum to 18 - 3 = 15 ways. This can happen
dp(x, 6, 15)ways.Die = 4.The remaining dice must sum to 18 - 4 = 14 ways. This can happen
dp(x, 6, 14)ways.Die = 5, The remaining dice must sum to 18 - 5 = 13 ways. This can happen
dp(x, 6, 13)ways.Die = 6.The remaining dice must sum to 18 - 6 = 12 ways. This can happen
dp(x, 6, 12)ways.
We sum up all these 6 cases to arrive at our We sum up the solutions these 6 cases to arrive at our result. Of course, each of these cases branches off into 6 cases of its own, and the recursion only resolves when d=0. The handling of this base case is explained below. .
The general relation is:
dp(d, f, target) = dp(d-1, f, target-1) + dp(d-1, f, target-2) + ... + dp(d-1, f, target-f)
The base case occurs when d = 0. We can make target=0 with 0 dice, but nothing else.
So dp(0, f, t) = 0 iff t != 0, and dp(0, f, 0) = 1.
Use memoization to avoid repeated calculations and don't conisider negative targets.
class Solution:
def numRollsToTarget(self, d: int, f: int, target: int) -> int:
memo = {}
def dp(d, target):
if d == 0:
return 0 if target > 0 else 1
if (d, target) in memo:
return memo[(d, target)]
to_return = 0
for k in range(max(0, target-f), target):
to_return += dp(d-1, k)
memo[(d, target)] = to_return
return to_return
return dp(d, target) % (10**9 + 7)Last updated