Skip to main content

Number of Dice Rolls With Target Sum

Problem statement​

You have n dice and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: n = 1, k = 6, target = 3Output: 1Explanation: You throw one die with 6 faces.There is only one way to get a sum of 3.

Example 2:

Input: n = 2, k = 6, target = 7Output: 6Explanation: You throw two dice, each with 6 faces.There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: n = 30, k = 30, target = 500Output: 222616187Explanation: The answer must be returned modulo 109 + 7.

Constraints:

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

My solution​

/**
 * @param {number} d
 * @param {number} f
 * @param {number} target
 * @return {number}
 */
const mod = Math.pow(10, 9) + 7;
const tracker = new Map();
var numRollsToTarget = function(d, f, target) {
    if (target < d || target > d * f) {
        return 0;
    }
    
    if (d === 1) {
        return target <= f ? 1 : 0;
    }
    
    const key = `${d}${f}${target}`;
    if (!tracker.get(key)) {
        let sum = 0;
        for (let i = 1; i <= f; i++) {
            sum += numRollsToTarget(d - 1, f, target - i);
            sum %= mod;
        }
        
        tracker.set(key, sum);
    }
    
    return tracker.get(key);
    
    
};