23. Dice throw

The problem can be found at the following link: ๐Ÿ”— Question Link

๐Ÿงฉ Problem Description

Given n dice, each having faces numbered from 1 to m, find the number of ways to get a total sum x when all the dice are thrown.

You must count every distinct sequence of face-up values (order matters).

You are given:

  • n dice,

  • each having m faces numbered from 1 to m,

  • and a target sum x.

Find the number of ways to get the sum x using the n dice. The result can be large, so return it modulo 10โน+7.

๐Ÿ“˜ Examples

Example 1:

Input:

m = 6, n = 3, x = 12

Output:

25

Explanation:

There are 25 distinct sequences of three 6-faced dice that sum up to 12.

Example 2:

Input:

m = 2, n = 3, x = 6

Output:

1

Explanation:

Only the sequence [2,2,2] sums to 6 when using three 2-faced dice.

๐Ÿ”’ Constraints

  • $1 \leq m, n, x \leq 50$

  • $1 \leq x \leq 2500$

โœ… My Approach

Classic 2D Dynamic Programming

We use a classic bottom-up dynamic programming strategy. Let dp[i][j] represent the number of ways to get sum j using i dice.

Recurrence Relation:

To get a sum of j with i dice, try all face values k = 1...m, and add ways to get j - k with i - 1 dice:

dp[i][j] = โˆ‘ dp[i-1][j-k] for all 1 โ‰ค k โ‰ค m and jโˆ’k โ‰ฅ 0

Algorithm Steps:

  1. Create a 2D vector dp[n+1][x+1] and initialize dp[0][0] = 1.

  2. Loop i from 1 to n (number of dice).

  3. Loop j from 1 to x (target sum).

  4. For each k from 1 to m, if j โ‰ฅ k, add dp[i-1][j-k] to dp[i][j].

  5. Return dp[n][x].

๐Ÿงฎ Time and Auxiliary Space Complexity

  • Time Complexity: O(n ร— x ร— m) We compute each state (i, j) using up to m previous states.

  • Auxiliary Space Complexity: O(n ร— x) We use a 2D DP table with n+1 rows and x+1 columns.

๐Ÿง‘โ€๐Ÿ’ป Code (C++)

class Solution {
  public:
    int noOfWays(int m, int n, int x) {
        const int mod = 1e9 + 7;
        vector<vector<int>> dp(n + 1, vector<int>(x + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= x; ++j)
                for (int k = 1; k <= m && k <= j; ++k)
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
        return dp[n][x];
    }
};
โšก Alternative Approaches

๐Ÿ“Š 2๏ธโƒฃ Space Optimized DP

Instead of using a 2D table, use two 1D arrays: dp and tmp.

Algorithm Steps:

  1. Use two 1D arrays dp and tmp, where dp[j] represents the number of ways to form sum j using i-1 dice.

  2. Initialize dp[0] = 1 since there's one way to reach sum 0 with 0 dice.

  3. For each die i from 1 to n, do the following:

    • Clear the tmp array.

    • For each target sum j from 1 to x:

      • Loop through each face value k from 1 to m (and k <= j) and accumulate ways from dp[j - k] to tmp[j].

  4. After processing a die, assign tmp to dp.

  5. Return dp[x], which holds the number of ways to get sum x with n dice.

class Solution {
  public:
    int noOfWays(int m, int n, int x) {
        const int mod = 1e9 + 7;
        vector<int> dp(x + 1), tmp(x + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fill(tmp.begin(), tmp.end(), 0);
            for (int j = 1; j <= x; ++j)
                for (int k = 1; k <= m && k <= j; ++k)
                    tmp[j] = (tmp[j] + dp[j - k]) % mod;
            dp = tmp;
        }
        return dp[x];
    }
};

โœ… Why This Approach?

  • Minimizes memory use with only two rows (1D arrays).

  • Retains full accuracy and efficiency of 2D dynamic programming.

  • Especially useful for large n and x.

๐Ÿ“ Complexity Analysis:

  • Time: O(n ร— x ร— m) โ€” Three nested loops for each die, each sum, and each face.

  • Auxiliary Space: O(x) โ€” Only two 1D arrays of size x + 1 are used.

๐Ÿ“Š 3๏ธโƒฃ Recursive + Memoization

Algorithm Steps:

Algorithm Steps:

  1. Use recursion to simulate choosing each face for every die.

  2. At each recursive call:

    • If n == 0, return 1 if x == 0, else return 0.

    • If x < 0, return 0 (invalid state).

    • Use memoization to store and reuse previously computed results.

  3. Try all face values from 1 to m and recurse with n - 1 dice and x - face.

class Solution {
  public:
    int dp[51][2501];
    int mod = 1e9 + 7;

    int solve(int n, int x, int m) {
        if (n == 0) return x == 0;
        if (x < 0) return 0;
        if (dp[n][x] != -1) return dp[n][x];
        int res = 0;
        for (int i = 1; i <= m; ++i)
            res = (res + solve(n - 1, x - i, m)) % mod;
        return dp[n][x] = res;
    }

    int noOfWays(int m, int n, int x) {
        memset(dp, -1, sizeof(dp));
        return solve(n, x, m);
    }
};

โœ… Why This Approach?

  • Naturally expresses the problem as a recursive decision tree.

  • Easy to understand, especially when learning recursion + memoization.

  • Less control over performance and higher overhead due to recursion stack.

๐Ÿ“ Complexity Analysis:

  • Time: O(n ร— x ร— m) โ€” Each state (n, x) is computed once with up to m choices.

  • Auxiliary Space: O(n ร— x) โ€” For memoization + recursion stack.

๐Ÿ†š Comparison of Approaches

Approach

โฑ๏ธ Time

๐Ÿ—‚๏ธ Space

โœ… Pros

โš ๏ธ Cons

๐Ÿ“ˆ Classic 2D DP

๐ŸŸข O(nยทxยทm)

๐Ÿ”ธ O(nยทx)

Easy to understand and implement

More space than needed

โžฟ Space-Optimized DP

๐ŸŸข O(nยทxยทm)

๐ŸŸข O(x)

Fast and memory-efficient

Slightly less intuitive

๐Ÿ” Recursive + Memoization

๐ŸŸข O(nยทxยทm)

๐Ÿ”ธ O(nยทx)

Good for learning and debugging

Stack overflow risk for large n

โœ… Best Choice by Scenario

Scenario

Recommended Approach

๐Ÿ† Minimize both time & memory

๐Ÿฅ‡ Space-Optimized DP

๐Ÿ“š Simplicity and clarity

๐Ÿฅˆ Classic 2D DP

๐Ÿ’ก Recursive problem-solving focus

๐Ÿฅ‰ Recursive + Memoization

๐Ÿง‘โ€๐Ÿ’ป Code (Java)

class Solution {
    static int noOfWays(int m, int n, int x) {
        int mod = (int)1e9 + 7;
        int[][] dp = new int[n + 1][x + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= x; ++j)
                for (int k = 1; k <= m && k <= j; ++k)
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
        return dp[n][x];
    }
}

๐Ÿ Code (Python)

class Solution:
    def noOfWays(self, m, n, x):
        mod = 10**9 + 7
        dp = [[0] * (x + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, x + 1):
                for k in range(1, min(m, j) + 1):
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod
        return dp[n][x]

๐Ÿง  Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: ๐Ÿ“ฌ Any Questions?. Letโ€™s make this learning journey more collaborative!

โญ If you find this helpful, please give this repository a star! โญ


๐Ÿ“Visitor Count

Last updated