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