1155. Number of Dice Rolls With Target Sum

Number of Dice Rolls With Target Sum

Problem Description

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 = 3
Output: 1

Explanation: 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 = 7
Output: 6

Explanation: 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 = 500
Output: 222616187

Explanation: The answer must be returned modulo 109 + 7.

 

Constraints:

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

Approach) DFS (Depth First Search) + memo

/**
 * @param {number} n
 * @param {number} k
 * @param {number} target
 * @return {number}
 */
const dfs = (d, f, target) => {
    if (d == 0) return target > 0 ? 0 : 1;
    let tmp = JSON.stringify([d, target]);
    if (memo.has(tmp)) return memo.get(tmp);
    let res = 0;
    for (let k = Math.max(0, target - f); k < target; k++) {
        res += dfs(d - 1, f, k);
        res %= mod;
    }
    memo.set(JSON.stringify([d, target]), res);
    return res;
};

const mod = 1e9 + 7;
let memo = new Map();

var numRollsToTarget = function(n, k, target) {
    memo = new Map();
    return dfs(n, k, target);
};

Runtime: 614 ms, faster than 20.49% of JavaScript online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 61.3 MB, less than 6.04% of JavaScript online submissions for Number of Dice Rolls With Target Sum.

Approach) Dynamic Programming

/**
 * @param {number} n
 * @param {number} k
 * @param {number} target
 * @return {number}
 */
const mod = 1e9 + 7;
const numRollsToTarget = (d, f, target) => {
    let dp = initialize2DArrayNew(d + 1, target + 1);
    dp[0][0] = 1;
    for (let i = 1; i <= d; i++) {
        for (let j = 1; j <= f; j++) {
            for (let k = j; k <= target; k++) {
                dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % mod;
            }
        }
    }
    return dp[d][target];
};

const initialize2DArrayNew = (m, n) => {
    let data = [];
    for (let i = 0; i < m; i++) {
        let tmp = new Array(n).fill(0);
        data.push(tmp);
    }
    return data;
};

Runtime: 162 ms, faster than 73.62% of JavaScript online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 44.4 MB, less than 86.26% of JavaScript online submissions for Number of Dice Rolls With Target Sum.

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1155. Number of Dice Rolls With Target Sum

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!