Number of Dice Rolls With Target Sum

class Solution {
public:
    const int MODULO = 1000000007;
        
    int diceRollSum(int diceCount, int faceCount, int desiredSum) {
        vector<vector<int>> dp(diceCount + 1, vector<int>(desiredSum + 1, 0));
        dp[diceCount][desiredSum] = 1;
            
        for (int dice = diceCount - 1; dice >= 0; dice--) {
            for (int sumSoFar = 0; sumSoFar <= desiredSum; sumSoFar++) {
               int countWays = 0;
                    
                for (int faceValue = 1; faceValue <= min(faceCount, desiredSum - sumSoFar); faceValue++) {
                    countWays = (countWays + dp[dice + 1][sumSoFar + faceValue]) % MODULO;
                }
                    
                dp[dice][sumSoFar] = countWays;
            }
        }
            
        return dp[0][0];
    }
};

This C++ solution addresses the problem of computing the number of distinct ways to roll a certain number of dice such that their sum equals a target value. Here, the function diceRollSum takes three parameters: diceCount, faceCount, and desiredSum. The method uses dynamic programming for efficient calculation.

• Initialize a 2D vector dp where dp[i][j] represents the number of ways to achieve a sum of j using the first i dice.

• Set dp[diceCount][desiredSum] to 1, indicating that there is exactly one way to reach the desiredSum with exactly diceCount dice: by each die showing a value that collectively adds up to desiredSum.

• Traverse from the last dice to the first in a nested loop structure. Loop through each possible sum thus far (sumSoFar), and calculate the number of ways to reach this sum using dice up to the current one (dice).

• Another nested loop examines each possible face value of a dice up to the minimum between the dice's maximum face (faceCount) and the remaining sum needed to reach the desired sum (desiredSum - sumSoFar).

• Calculate countWays by summing up all possible ways to achieve the required sumSoFar+faceValue with the remaining dice.

• Update each state in dp[dice][sumSoFar] by setting it to countWays.

• Use modulo operation with MODULO (10^9 + 7) to prevent integer overflow and maintain the results within the specified limit.

The final result, dp[0][0], gives the number of ways to obtain the desiredSum from all diceCount dice, starting from a sum of zero. This approach ensures that calculations are manageable and efficient by leveraging the overlapping subproblems using dynamic programming.

class Solver {
    final int MODULO = 1000000007;
    
    public int calculateNumberOfWays(int dice, int faces, int sum) {
        int[][] dp = new int[dice + 1][sum + 1];
        dp[dice][sum] = 1;
    
        for (int idx = dice - 1; idx >= 0; idx--) {
            for (int currentSum = 0; currentSum <= sum; currentSum++) {
                int countWays = 0;
    
                for (int faceValue = 1; faceValue <= Math.min(faces, sum - currentSum); faceValue++) {
                    countWays = (countWays + dp[idx + 1][currentSum + faceValue]) % MODULO;
                }
    
                dp[idx][currentSum] = countWays;
            }
        }
    
        return dp[0][0];
    }
}

In the solution presented, you achieve the goal of calculating the number of ways to roll a set of dice to achieve a specific target sum. This approach utilizes dynamic programming to efficiently solve the problem using a Java method named calculateNumberOfWays inside the Solver class. Here's a breakdown of how this method functions:

• Initialization: An array dp is initialized with (dice + 1) rows and (sum + 1) columns, filled with zeros. It utilizes dynamic programming to store intermediate results, where dp[i][j] represents the number of ways to obtain a sum j using the first i dices.

• Base Case Setting: The code sets dp[dice][sum] to 1, establishing the base case that there is exactly one way to achieve the target sum using all the dice if that exact sum is reached.

• Iterative Computation:

  • Loop through each die from the last one to the first (for loop moving backwards).
  • For every possible sum from 0 to the target sum, compute the number of ways the sum can be gathered.
  • A nested loop then iterates over all possible face values that each die can show. It adds up ways from subsequent states, making sure not to exceed the number of available faces or the sum decrementing as necessary for the recursion.
  • The modulo operation ensures that the results are within manageable numeric limits, preventing integer overflow.

• Final Return: After populating the dp array, dp[0][0] gives the total number of ways to achieve the target sum with the given number of dice. This outcome represents the solution to the problem.

This dynamic programming solution effectively reduces the complexity of the problem from exponential in nature, typical with recursive approaches, to polynomial with respect to the number of dice and the target sum. This ensures the method is efficient and scales well with larger inputs.