Leetcode 1155. Number of Dice Rolls With Target Sum

Problem Explanation

Given d dice, each with f faces numbered from 1 to f, the goal is to find the total number of ways to roll the dice such that the sum of the face-up numbers is equal to target. This is done with the constraint that the result should be modulo 10^9 + 7.

This problem is essentially asking us to calculate the number of combinations of rolling d dice (with f faces) that will give a sum of target.

For instance, if one die is thrown (d = 1) with 6 faces (f = 6), and the target sum is 3 (target = 3), the answer is 1 because there's only one way for the sum of the face up number to be 3 (i.e. rolling a 3).

Solution Approach

This problem can be solved using the Dynamic Programming approach. Specifically, we can use a unique form of the knapsack problem variant, called the unbounded knapsack problem, where items may be used/selected more than once.

We can consider d as the number of selections allowed (equivalent to the number of dice rolled). Each die roll has f possible choices (equivalent to the faces on each die). And the sum obtained from rolling the dice (target) is equivalent to the weight/value we want to obtain in the knapsack problem.

First, we initialize a list dp (dynamic programming list) of size target + 1 with all zeros, except that dp[0] is set to 1. dp[i] will represent the number of ways to sum up to i with d dice.

Then, we use a nested loop to go over each dice (d) and calculate the possible number i that can be rolled and the ways to get to the value target. We create a new list newDp to store the current state of the dynamic programming list. And at each loop of the number i, we update newDp[t] which is the count at index t.

Finally, we move the values from newDp back to dp and continue to the next dice.

In the end, dp[target] will have the result i.e., the number of ways we can roll the dice to get a sum of target.

One key point to remember is to take the result modulo 10^9 + 7 before returning, to prevent overflow and fit the problem constraints.

Python Solution

1
2python
3class Solution:
4    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
5        mod = 10**9 + 7
6        dp = [1] + [0] * target 
7        for _ in range(d): 
8            dp = [sum(dp[max(0, i - f): i]) % mod for i in range(target + 1)] 
9        return dp[target]

Java Solution

1
2java
3class Solution {
4    public int numRollsToTarget(int d, int f, int target) {
5        int kMod = 1000000007;
6        int[] dp = new int[target + 1];
7        dp[0] = 1;
8
9        for (int i = 0; i < d; i++) {
10            int[] newDp = new int[target + 1];
11            for (int j = 1; j <= f; j++) {
12                for (int k = j; k <= target; k++) {
13                    newDp[k] += dp[k - j];
14                    newDp[k] %= kMod;
15                }
16            }
17            dp = newDp;
18        }
19        return dp[target];
20    }
21}

JavaScript Solution

1
2javascript
3var numRollsToTarget = function(d, f, target) {
4    const dp = Array(d+1).fill(0).map(v => Array(target+1).fill(0));
5    const mod = Math.pow(10, 9) + 7;
6    dp[0][0] = 1;
7    for(let i=1; i<=d; i++){
8        for(let j=1; j<=target; j++){
9            for(let k=1; k<=f; k++){
10                if(j >= k) dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod;
11            }
12        }
13    }
14    return dp[d][target];
15};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numRollsToTarget(int d, int f, int target) {
6        int mod = pow(10, 9) + 7;
7        vector<vector<int>> dp(d+1, vector<int>(target+1, 0));
8        
9        for(int i=1; i<=min(f, target); i++) { // for target = i, only one dice is needed
10            dp[1][i] = 1;
11        }
12        
13        for(int i=2; i<=d; i++) {
14            for(int j=1; j<=target; j++) {
15                for(int k=1; k<=f; k++) {
16                    if(j > k) {
17                        dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod;
18                    }
19                    else if(j == k) {
20                        dp[i][j] = (dp[i][j] + 1) % mod;
21                    }
22                }
23            }
24        }
25        
26        return dp[d][target];
27    }
28};

C# Solution

1
2csharp
3public class Solution {
4    public int NumRollsToTarget(int d, int f, int target) {
5        int mod = (int)Math.Pow(10, 9) + 7;
6        int[,] dp = new int[d+1, target+1];
7        
8        dp[0,0] = 1;
9        
10        for(int i = 1; i <= d; i++){
11            for(int j = 1; j <= target; j++){
12                for(int k = 1; k <= f; k++){
13                    if(j >= k) {
14                        dp[i, j] = (dp[i, j] + dp[i - 1, j - k]) % mod;
15                    }
16                }
17            }
18        }
19        return dp[d, target];
20    }
21}

The solution in each language follows the same approach, using dynamic programming to solve the problem in an optimal way. This approach ensures that calculations are not repeated, resulting in efficient code.

The nested loops go through each combination of dice and faces, and for each combination, calculate how many ways we can get to the target sum.## Complexity Analysis

Time Complexity

The time complexity of the solution is O(d * f * target). This is because for each dice, the solution iterates over each face and for each face, it goes up to the target sum to compute the number of ways to get to the target. Hence, in the worst case, the time complexity is proportional to the product of the number of dice, the number of faces, and the target sum.

Space Complexity

The space complexity of the solution is O(target). This is because a dynamic programming list of size target + 1 is used to store the intermediate results.

The space complexity could also be O(d * target) if we consider the programming solutions that use a two dimensional array to store the results for each dice and sum. However, in the above solutions, we optimize the space by using a one dimensional array and overwrite its content for each dice.

Although this problem might seem complex at first glance, it is quite manageable once broken down and approached in a systematic way. Understanding the underlying concepts of Dynamic Programming and how it applies to problems like these is key to finding such elegant solutions.

You may need to practice a few similar problems to get familiar with this concept. But once you master it, you'd be amazed at how many problems can be solved using these principles. Happy coding!

---

Additional reading:

1. Dynamic Programming: https://en.wikipedia.org/wiki/Dynamic_programming
2. Knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem