Problem Description

Given n dice, each with k faces numbered from 1 to k, you are to find out in how many ways you can roll the dice so that the sum of the face-up numbers equals the given target. The answer can be large, so return it modulo 109 + 7.

• n: the number of dice.
• k: the number of faces on each die (faces are 1 to k).
• target: the required sum of the dice faces.

Constraints:

• Each die can show any number from 1 to k on its face.
• You must use all n dice.
• The order of dice is not important; only the sum matters.
• Return the number of possible ways modulo 109 + 7.

Thought Process

At first glance, you might think of generating all possible outcomes for rolling n dice and counting those whose sum is target. But with increasing n and k, the number of combinations grows exponentially, making brute-force infeasible.

Instead, notice that this is a classic combinatorial problem where order does not matter, but the sum does. This hints at using dynamic programming (DP): for each die, keep track of the number of ways to reach every possible sum up to target. By breaking the problem into smaller, overlapping subproblems and storing intermediate results, we avoid redundant calculations and make the solution efficient.

Solution Approach

We'll use a dynamic programming approach with the following steps:

1. Define DP State: Let dp[i][t] be the number of ways to get sum t using i dice.
2. Base Case: There is 1 way to get sum 0 with 0 dice: dp[0][0] = 1.
3. Transition: For each die (from 1 to n), and for each possible sum (from 1 to target), try every possible face value (f from 1 to k). If t - f is non-negative, then add dp[i-1][t-f] to dp[i][t].
4. Result: The answer is dp[n][target].
5. Modulo: Since the answer can be huge, we take all calculations modulo 109 + 7.

We use a 2D array for DP, but it can be optimized to 1D since each state only depends on the previous number of dice.

Example Walkthrough

Let's work through an example: n = 2, k = 6, target = 7.

• We want the number of ways to roll two dice so their sum is 7.
• Possible pairs: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1). That's 6 ways.
• Using DP:
  • For 1 die, dp[1][s] is 1 for s from 1 to 6 (each face), 0 otherwise.
  • For 2 dice, to get sum 7:
    • Try all faces for the second die (f): for each f from 1 to 6, add dp[1][7-f] to dp[2][7] if 7-f is between 1 and 6.
    • Each dp[1][7-f] is 1 if 7-f is 1..6.
    • So, dp[2][7] = 1 + 1 + 1 + 1 + 1 + 1 = 6.

The DP table correctly counts all combinations.

Time and Space Complexity

Brute-force: Would require checking k^n combinations, which is exponential and infeasible for large n.

Dynamic Programming:

• Time Complexity: O(n * target * k) because for each of the n dice and each possible sum up to target, we try all k faces.
• Space Complexity: O(n * target) for the DP table. This can be optimized to O(target) with a rolling array.

Summary

The problem is a classic example of using dynamic programming to count the number of ways to achieve a sum with dice rolls. By breaking the problem into smaller subproblems and building up solutions, we avoid the exponential blowup of brute-force approaches. The DP approach is efficient, elegant, and easily generalizable to similar counting problems.

Code Implementation

MOD = 10**9 + 7
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for dice in range(1, n + 1):
            new_dp = [0] * (target + 1)
            for t in range(1, target + 1):
                for f in range(1, k + 1):
                    if t - f >= 0:
                        new_dp[t] = (new_dp[t] + dp[t - f]) % MOD
            dp = new_dp
        return dp[target]
      

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        const int MOD = 1e9 + 7;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int dice = 1; dice <= n; ++dice) {
            vector<int> new_dp(target + 1, 0);
            for (int t = 1; t <= target; ++t) {
                for (int f = 1; f <= k; ++f) {
                    if (t - f >= 0) {
                        new_dp[t] = (new_dp[t] + dp[t - f]) % MOD;
                    }
                }
            }
            dp = new_dp;
        }
        return dp[target];
    }
};
      

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        int MOD = 1000000007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int dice = 1; dice <= n; dice++) {
            int[] new_dp = new int[target + 1];
            for (int t = 1; t <= target; t++) {
                for (int f = 1; f <= k; f++) {
                    if (t - f >= 0) {
                        new_dp[t] = (new_dp[t] + dp[t - f]) % MOD;
                    }
                }
            }
            dp = new_dp;
        }
        return dp[target];
    }
}
      

var numRollsToTarget = function(n, k, target) {
    const MOD = 1e9 + 7;
    let dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (let dice = 1; dice <= n; dice++) {
        let new_dp = new Array(target + 1).fill(0);
        for (let t = 1; t <= target; t++) {
            for (let f = 1; f <= k; f++) {
                if (t - f >= 0) {
                    new_dp[t] = (new_dp[t] + dp[t - f]) % MOD;
                }
            }
        }
        dp = new_dp;
    }
    return dp[target];
};