medium Number of Dice Rolls With Target Sum

Problem Statement

You are given n dice, each dice having k faces numbered from 1 to k. You are also given target positive integer.

Return the number of ways you can roll the dice so that the sum of the face-up numbers equals the target sum. Since the answer may be too large, return it modulo 10⁹ + 7.

Examples

Example 1

• Input: n = 2, k = 4, target = 5
• Expected Output: 4
• Justification: The possible rolls are (1, 4), (2, 3), (3, 2), and (4, 1).

Example 2

• Input: n = 3, k = 6, target = 8
• Expected Output: 21
• Justification: There are 21 combinations of rolling three dice with faces from 1 to 6 that sum up to 8.

Example 3

• Input: n = 1, k = 2, target = 2
• Expected Output: 1
• Justification: The only possible roll is (2).

Constraints:

• 1 <= n, k <= 30
• 1 <= target <= 1000

Solution

To solve this problem, we use dynamic programming (DP). Dynamic programming helps us store intermediate results to avoid redundant calculations. We can think of this problem as a way to count paths in a graph where each step represents rolling a dice face. The state can be defined as the number of ways to achieve a particular sum using a specific number of dice. We build this state incrementally, considering the result of adding each face of the dice to the possible sums from the previous state. This way, we efficiently explore all combinations.

This approach is effective because it reduces the problem to a manageable size, breaking it down into smaller subproblems. By storing results of subproblems, we avoid recomputation and handle the large number of possible combinations efficiently, keeping our solution within a feasible time complexity.

Step-by-step Algorithm

1. Initialize the DP Table:

   • Create a 2D array dp with dimensions (n+1) x (target+1).
   • Set dp[0][0] = 1 because there is one way to achieve a sum of 0 with 0 dice (by not rolling any dice).

2. Iterate Over Number of Dice:

   • For each dice from 1 to n:
     • For each possible sum from 1 to target:
       • For each face value from 1 to k:
         • If the current sum (j) is greater than or equal to the face value (face):
           • Update dp[i][j] by adding the number of ways to achieve the sum j - face using i-1 dice: dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD.

3. Return Result:

   • Return dp[n][target] which represents the number of ways to achieve the target sum using n dice.

Algorithm Walkthrough

Input: n = 2, k = 4, target = 5

Step-by-step Execution:

1. Initialize the DP Table:

   • Create a 3 x 6 DP table initialized to 0.
   • Set dp[0][0] = 1.

   Initial DP table:

   dp = [[1, 0, 0, 0, 0, 0], 
         [0, 0, 0, 0, 0, 0], 
         [0, 0, 0, 0, 0, 0]]
   

2. Iterate Over the Number of Dice (i):

   • For i = 1 (1 dice):

     • For j = 1 to 5 (possible sums):
       • For face = 1 to 4 (faces of the dice):
         • Update the DP table:

           • j = 1: face = 1:

             dp[1][1] = dp[1][1] + dp[0][0] = 0 + 1 = 1
             

           • j = 2: face = 1, 2:

             dp[1][2] = dp[1][2] + dp[0][1] = 0 + 0 = 0
             dp[1][2] = dp[1][2] + dp[0][0] = 0 + 1 = 1
             

           • j = 3: face = 1, 2, 3:

             dp[1][3] = dp[1][3] + dp[0][2] = 0 + 0 = 0
             dp[1][3] = dp[1][3] + dp[0][1] = 0 + 0 = 0
             dp[1][3] = dp[1][3] + dp[0][0] = 0 + 1 = 1
             

           • j = 4: face = 1, 2, 3, 4:

             dp[1][4] = dp[1][4] + dp[0][3] = 0 + 0 = 0
             dp[1][4] = dp[1][4] + dp[0][2] = 0 + 0 = 0
             dp[1][4] = dp[1][4] + dp[0][1] = 0 + 0 = 0
             dp[1][4] = dp[1][4] + dp[0][0] = 0 + 1 = 1
             

           • j = 5: face = 1, 2, 3, 4:

             dp[1][5] = dp[1][5] + dp[0][4] = 0 + 0 = 0
             dp[1][5] = dp[1][5] + dp[0][3] = 0 + 0 = 0
             dp[1][5] = dp[1][5] + dp[0][2] = 0 + 0 = 0
             dp[1][5] = dp[1][5] + dp[0][1] = 0 + 0 = 0
             

     Updated DP table after 1 dice:

     dp = [[1, 0, 0, 0, 0, 0], 
           [0, 1, 1, 1, 1, 0], 
           [0, 0, 0, 0, 0, 0]]
     

   • For i = 2 (2 dice):

     • For j = 1 to 5 (possible sums):
       • For face = 1 to 4 (faces of the dice):
         • Update the DP table:

           • j = 1: face = 1:

             dp[2][1] = dp[2][1] + dp[1][0] = 0 + 0 = 1
             

           • j = 2: face = 1, 2:

             dp[2][2] = dp[2][2] + dp[1][1] = 0 + 1 = 1
             dp[2][2] = dp[2][2] + dp[1][0] = 1 + 0 = 1
             

           • j = 3: face = 1, 2, 3:

             dp[2][3] = dp[2][3] + dp[1][2] = 0 + 1 = 1
             dp[2][3] = dp[2][3] + dp[1][1] = 1 + 1 = 2
             dp[2][3] = dp[2][3] + dp[1][0] = 2 + 0 = 2
             

           • j = 4: face = 1, 2 ,3, 4:

             dp[2][4] = dp[2][4] + dp[1][3] = 0 + 1 = 1
             dp[2][4] = dp[2][4] + dp[1][2] = 1 + 1 = 2
             dp[2][4] = dp[2][4] + dp[1][1] = 2 + 1 = 3
             dp[2][4] = dp[2][4] + dp[1][0] = 3 + 0 = 3
             

           • j = 5: face = 1, 2, 3, 4:

             dp[2][5] = dp[2][5] + dp[1][4] = 0 + 1 = 1
             dp[2][5] = dp[2][5] + dp[1][3] = 1 + 1 = 2
             dp[2][5] = dp[2][5] + dp[1][2] = 2 + 1 = 3
             dp[2][5] = dp[2][5] + dp[1][1] = 3 + 1 = 4
             

     Updated DP table after 2 dice:

     dp = [[1, 0, 0, 0, 0, 0], 
           [0, 1, 1, 1, 1, 0], 
           [0, 0, 1, 2, 3, 4]]
     

3. Return Result:

   • Return dp[2][5], which is 4.

Code

class Solution {

  public int numRollsToTarget(int n, int k, int target) {
    // Define the modulo value
    int MOD = 1000000007;

    // Initialize the dp array
    int[][] dp = new int[n + 1][target + 1];

    // Base case: one way to get sum 0 with 0 dice
    dp[0][0] = 1;

    // Loop over the number of dice
    for (int i = 1; i <= n; i++) {
      // Loop over the possible sums
      for (int j = 1; j <= target; j++) {
        // Loop over the faces of the dice
        for (int face = 1; face <= k; face++) {
          // If the current sum is at least the face value
          if (j >= face) {
            // Update the dp array with the number of ways to achieve the sum
            dp[i][j] = (dp[i][j] + dp[i - 1][j - face]) % MOD;
          }
        }
      }
    }

    // Return the number of ways to achieve the target sum with n dice
    return dp[n][target];
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test case 1
    System.out.println(solution.numRollsToTarget(2, 4, 5)); // Output: 4
    // Test case 2
    System.out.println(solution.numRollsToTarget(3, 6, 8)); // Output: 21
    // Test case 3
    System.out.println(solution.numRollsToTarget(1, 2, 2)); // Output: 1
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is . Here's the breakdown:

• We loop over the number of dice (n).
• For each dice, we loop over the possible sums (target).
• For each sum, we loop over the faces of the dice (k).

Therefore, the time complexity is .

Space Complexity

The space complexity of the algorithm is . Here's the breakdown:

• We use a 2D array dp with dimensions (n + 1) x (target + 1) to store the number of ways to achieve each sum with a certain number of dice.

Therefore, the space complexity is .