Number Of Dice Rolls With Target Sum - Leetcode Solution

The problem statement reads:

You have d dice and each die has f faces numbered 1 to f. You are given a target sum target. You have to find the number of possible ways to roll the dice to get the target sum.

The brute-force approach to solve this problem is to generate all possible combinations of throwing the d dice with their respective f faces and add up the ones whose sum equals target. However, given the constraints of the problem (1 ≤ d, f ≤ 30, 1 ≤ target ≤ 1000), this approach will take a long time to execute.

A better approach to solve this problem is Dynamic Programming (DP). We will create a 2D array dp[][] of dimensions (d+1) x (target+1) where dp[i][j] will represent the number of ways to achieve the target sum j using i dice.

For the base cases, we initialize dp[0][0] to 1 (since no dice are required to throw and the sum is already zero) and initialize the rest of dp[0][j] as 0 (since no dice are thrown, no sum can be achieved). Similarly, we initialize dp[i][0] as 0 (since with i dice, the sum can never be zero).

The recurrence relation to compute dp[i][j] will be as follows. For each die k (k ranges from 1 to f) thrown by the current player, we add to the sum k and check how many ways we can achieve the remaining sum of j - k. The number of ways to achieve the remaining sum will be dp[i-1][j-k]. We sum over all possible dice values to compute dp[i][j].

Therefore, the recurrence relation will be as follows:

dp[i][j] = dp[i][j] + dp[i-1][j-k] for all k such that 1 ≤ k ≤ f and j-k ≥ 0.

The final answer will be the value of dp[d][target].

The time complexity of this approach is O(d x f x target) and the space complexity is O(d x target).

Code:

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        int dp[d+1][target+1]; // dp[i][j] represents the number of ways to achieve target j using i die
        memset(dp, 0, sizeof(dp));
        
        dp[0][0] = 1; // Base case
        
        for(int i = 1; i <= d; i++) {
            for(int j = 1; j <= target; j++) {
                for(int k = 1; k <= f; k++) {
                    if(j - k >= 0) {
                        dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % 1000000007;
                    }
                }
            }
        }
        
        return dp[d][target];
    }
};

Reference: Number of Dice Rolls With Target Sum

1