1155. Number of Dice Rolls With Target Sum
Problem Description
In this problem, we are working with a scenario involving n
dice, each having k
faces numbered from 1 to k
. We want to figure out how many different ways we can roll these dice so that the sum of the numbers showing on the tops of all dice equals a specific target
value. To clarify, there are a total of k^n
different roll combinations since each die can land on any of its k
faces and we have n
dice in total. The challenge is to filter out and count only those combinations where the sum equals target
. Because the number of possible ways can get extremely large, the result should be provided modulo 10^9 + 7
to avoid overflow issues.
Intuition
The core of the solution lies in dynamic programming, a method that involves breaking down a complex problem into smaller, more manageable subproblems and building up the solution from the answers to these subproblems.
The main idea is to keep track of the number of ways to achieve a certain sum using a particular number of dice. To do this, we define a state f[i][j]
, which represents the count of ways to reach a sum of j
using i
dice. We start from the base case where no dice are used, so the only possible sum of zero is to have zero dice (which is one way).
From there, we incrementally build up by considering one more die at each step. For every number of dice i
from 1 to n
and for each possible sum j
up to the target
, we determine the number of ways to achieve that sum by considering all the possible outcomes of the new die. In simple terms, for every possible value h
that the new die could land on, we add the number of ways to achieve the sum j - h
using i - 1
dice to our current count.
Through these iterations, we build a table of values reflecting the different ways to reach the sum, all the way up to using all n
dice to reach the target
sum. The final answer is then the value stored in f[n][target]
.
The given solution cleverly optimizes the space complexity by using a single-dimensional array f[]
, where the values of the previous iteration are used to calculate the values of the current iteration. As each value is computed, it is stored back in f[]
after considering all possible faces of the current die. This is done to ensure that we are neither running out of memory due to a large number of subproblems nor repeating the calculation for the same subproblems multiple times.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution involves a two-dimensional problem being solved using a one-dimensional array to save space. The mathematical formula that guides the solution is:
1f[i][j] = sum(f[i-1][j-h] for h in range(1, min(j, k)+1))
This equation is the heart of our dynamic programming approach, where f[i][j]
is the number of ways to get a sum of j
using i
dice. However, instead of using a two-dimensional array, we optimize the solution by reusing a single array f
where f[j]
at any point contains the number of ways to reach sum j
with the current number of dice considered.
The innermost loop runs through all the possible face values (h
) of the current die (up to k
, but not more than j
since we can't have the face value of a die be more than the sum we're trying to achieve). For each face value, it adds to the temporary array g[j]
the number of ways we can achieve the remaining sum (j - h
) with one less die, modulo 10^9 + 7
to prevent overflow.
After each die is considered (outer loop), the f
array is updated to be the temporary array g
for the next iteration, effectively moving from analyzing i-1
dice to i
dice while preserving the required state and avoiding the direct use of a two-dimensional array.
Here is an implementation perspective that breaks down each part of the code:
-
Initialization: An array
f
is initialized with sizetarget + 1
, starting withf[0] = 1
and the rest0
. This reflects the base case where a sum of0
can be achieved in one way with zero dice. -
Building up solutions for each die:
- A temporary array
g
is initialized to hold the number of ways to reach every possible sum up totarget
with one additional die. - We iterate over each sum
j
that could be reached with the current number (i
) of dice. - For each
j
, we calculateg[j]
based on previous sums computed inf
.
- A temporary array
-
Updating state: After considering all sums for the current die, we make
f = g
to update our state without using additional space for a second dimension. -
Return the answer: After considering all
n
dice,f[target]
gives us the final number of ways to reach thetarget
sum. -
Modulus Operation: A
mod
constant is used at each step of the calculation to ensure the number stays within the specified range,10^9 + 7
.
By iterating through dice and potential sums in this manner, the dynamic programming approach efficiently calculates the number of ways to roll the dice to reach a targeted sum.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using an example where we have n = 2
dice and each die has k = 3
faces numbered from 1 to 3. We want to find out how many ways we can roll the dice so that the sum is equal to the target
value of 4.
-
Initialization: We initialize an array
f
with a length oftarget + 1
, which meansf
has a size of 5 in this case (0, 1, 2, 3, 4) sincetarget
is 4. We havef = [1, 0, 0, 0, 0]
. -
Considering the first die: We create a temporary array
g
which will be used to compute the sums reachable with one die. Forj = 1
totarget
(which is 4 in this example), we calculate the number of ways to reach the sumj
by adding the face values of the die tof[j - h]
, whereh
ranges from 1 tomin(j, k)
.- For
j = 1
,g[1] = f[1 - 1] = f[0] = 1
(f[0]
initialized as 1). - For
j = 2
,g[2] = f[2 - 1] = f[1] = 1
(since we could roll a 2 on the first die). - For
j = 3
,g[3] = f[3 - 1] = f[2] = 1
(rolling a 3 on the first die). - For
j = 4
, since the maximum face value (k) is 3, we cannot achieve a sum of 4 with one die, sog[4] = 0
. After considering the first die,f
gets updated tof = g = [1, 1, 1, 1, 0]
.
- For
-
Considering the second die: We repeat the process with the second die.
- For
j = 1
, there's no change as we can't add a positive face value to reach 1 without exceeding it. - For
j = 2
,g[2]
will now include the number of ways to reach a sum of1
from the first die and then roll a1
on the second die, which is just reusing previousf[1] = 1
. - For
j = 3
,g[3]
will include the ways to reach sums of2
and1
from the first die and rolling1
or2
on the second die, respectively. Thus,g[3] = f[2] + f[1] = 1 + 1 = 2
. - For
j = 4
, we sum the ways to get3
,2
, and1
with the first die and roll1
,2
, or3
on the second die:g[4] = f[3] + f[2] + f[1] = 1 + 1 + 1 = 3
. Now,f
is updated tof = g = [1, 1, 1, 2, 3]
.
- For
-
Return the answer: After considering all
n
dice, in this case, two dice, the final computation for each sum is done. The final answer isf[target]
, which isf[4]
in this case, so there are 3 different ways to roll the dice to get the sum of 4.
By using this approach, we have efficiently computed the desired sum without needing a two-dimensional array, thus optimizing our space usage. For larger values of n
and k
, following the same steps while considering the modulo 10^9 + 7
would ensure we avoid integer overflow issues.
Solution Implementation
1class Solution:
2 def numRollsToTarget(self, dice: int, sides: int, target: int) -> int:
3 # Initialize the array of ways to achieve each sum, with 1 way to achieve a sum of 0
4 ways_to_achieve_sum = [1] + [0] * target
5 # Define the modulo according to the problem statement to avoid large numbers
6 modulo = 10**9 + 7
7
8 # Iterate through each dice
9 for i in range(1, dice + 1):
10 # Initialize the temporary array for the current dice's sum calculations
11 current_ways = [0] * (target + 1)
12 # Calculate the number of ways to achieve each sum with the current number of dice
13 for sum_value in range(1, min(i * sides, target) + 1):
14 # Calculate the ways to get to this sum_value using the previous number of dice
15 for face_value in range(1, min(sum_value, sides) + 1):
16 current_ways[sum_value] = (current_ways[sum_value] + ways_to_achieve_sum[sum_value - face_value]) % modulo
17 # Update the array of ways with the current dice's calculation
18 ways_to_achieve_sum = current_ways
19
20 # Return the total number of ways to achieve the target sum with all dice
21 return ways_to_achieve_sum[target]
22
1class Solution {
2 public int numRollsToTarget(int n, int k, int target) {
3 final int MODULO = (int) 1e9 + 7; // Define the modulo to prevent integer overflow
4 int[] dp = new int[target + 1]; // dp array to store the number of ways to achieve each sum
5 dp[0] = 1; // Base case: there's 1 way to achieve sum 0 - no dice rolled
6
7 // Loop through each dice
8 for (int diceCount = 1; diceCount <= n; ++diceCount) {
9 int[] tempDp = new int[target + 1]; // Temporary array for the current number of dices
10
11 // Calculate number of ways for each sum value possible with the current number of dices
12 for (int currentSum = 1; currentSum <= Math.min(target, diceCount * k); ++currentSum) {
13
14 // Go through each face value of the dice and accumulate ways to achieve 'currentSum'
15 for (int faceValue = 1; faceValue <= Math.min(currentSum, k); ++faceValue) {
16 tempDp[currentSum] = (tempDp[currentSum] + dp[currentSum - faceValue]) % MODULO;
17 }
18 }
19
20 // Update the dp array with the current number of dices' results
21 dp = tempDp;
22 }
23
24 // Return the number of ways to achieve the 'target' sum with 'n' dices
25 return dp[target];
26 }
27}
28
1class Solution {
2public:
3 // Function to calculate the number of distinct ways to roll the dice
4 // such that the sum of the face-up numbers equals to 'target'
5 int numRollsToTarget(int numberOfDice, int faces, int targetSum) {
6 const int MODULO = 1e9 + 7; // Modulo for avoiding integer overflow
7
8 // Create a dynamic programming table initialized with zeros,
9 // `dp[currentTarget]` will represent the number of ways to get sum `currentTarget`
10 vector<int> dp(targetSum + 1, 0);
11
12 // Base case: one way to reach sum 0 - by not choosing any dice
13 dp[0] = 1;
14
15 // Iterate over the number of dice
16 for (int i = 1; i <= numberOfDice; ++i) {
17 // Temporary vector to store ways to reach a certain sum with the current dice
18 vector<int> newDp(targetSum + 1, 0);
19
20 // Calculate number of ways to get each sum from 1 to `targetSum` with `i` dice
21 for (int currentSum = 1; currentSum <= min(targetSum, i * faces); ++currentSum) {
22 // Look back at most `faces` steps to find the number of ways to
23 // reach the current sum from previous sums using different face values
24 for (int faceValue = 1; faceValue <= min(currentSum, faces); ++faceValue) {
25 newDp[currentSum] = (newDp[currentSum] + dp[currentSum - faceValue]) % MODULO;
26 }
27 }
28
29 // Move the updated values in `newDp` to `dp` for the next iteration
30 dp = move(newDp);
31 }
32
33 // Final answer is the number of ways to reach `targetSum` with `numberOfDice` dice
34 return dp[targetSum];
35 }
36};
37
1function numRollsToTarget(diceCount: number, facesPerDie: number, targetSum: number): number {
2 // Initialize a dynamic programming array to keep track of ways to reach each sum
3 const waysToTarget = Array(targetSum + 1).fill(0);
4 waysToTarget[0] = 1; // There is 1 way to reach the sum 0 (rolling no dice)
5
6 // Define a modulus constant to prevent integer overflow
7 const mod = 1e9 + 7;
8
9 // Iterate over each die
10 for (let currentDie = 1; currentDie <= diceCount; ++currentDie) {
11 // Temporary array to calculate the current number of ways to achieve each sum
12 const tempWays = Array(targetSum + 1).fill(0);
13
14 // Calculate for all possible sums up to the current target
15 // constrained by the number of dice thrown so far and the desired target
16 for (let currentTarget = 1; currentTarget <= Math.min(currentDie * facesPerDie, targetSum); ++currentTarget) {
17 // Check for all the possible outcomes of a single die roll and update
18 for (let faceValue = 1; faceValue <= Math.min(currentTarget, facesPerDie); ++faceValue) {
19 // Update the ways to achieve currentTarget sum considering the current die roll
20 tempWays[currentTarget] = (tempWays[currentTarget] + waysToTarget[currentTarget - faceValue]) % mod;
21 }
22 }
23
24 // Update the original waysToTarget array with the computed values for the current die roll
25 waysToTarget.splice(0, targetSum + 1, ...tempWays);
26 }
27
28 // Return the number of ways to reach the desired target sum using all the dice
29 return waysToTarget[targetSum];
30}
31
Time and Space Complexity
The given Python code is solving the problem of finding the number of distinct ways to roll a set of dice so that the sum of the faces equals the target sum.
Time Complexity:
The time complexity of the code can be analyzed based on the nested loops present in the function:
- There is an outer loop running
n
iterations wheren
is the number of dice. - The first inner loop iterates up to
min(i * k, target)
. Sincei
goes from1
ton
, in the worst case, this loop runstarget
times. - The second inner loop iterates up to
min(j, k)
. In the worst case,j
can betarget
, this loop runsk
times.
In the worst case, the time complexity of the algorithm will be O(n * target * k)
.
Space Complexity:
Based on the reference answer and the code provided, we are using a rolling array (f
) to represent the states, which has a size of target + 1
.
f
andg
arrays both are of sizetarget + 1
, but they are reused in every iteration instead of creating a 2D array of sizen * target
.
Hence, the space complexity of the algorithm is O(target)
, as only a single-dimensional array is used which is proportional to the target
value.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.