07. Dice Throw

✅ GFG solution to Dice Throw: count number of ways to get target sum using n dice with m faces using dynamic programming. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

Given n dice each with m faces, find the number of ways to get sum x which is the summation of values on each face when all the dice are thrown.

📘 Examples

Example 1

Input: m = 6, n = 3, x = 12
Output: 25
Explanation: There are 25 total ways to get the sum 12 using 3 dice with faces from 1 to 6.

Example 2

Input: m = 2, n = 3, x = 6
Output: 1
Explanation: There is only 1 way to get the sum 6 using 3 dice with faces from 1 to 2. 
All the dice will have to land on 2.

Example 3

Input: m = 6, n = 2, x = 7
Output: 6
Explanation: Ways are (1,6), (2,5), (3,4), (4,3), (5,2), (6,1).

🔒 Constraints

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

✅ My Approach

The optimal solution uses Space-Optimized Dynamic Programming:

1D DP with Backward Iteration

1. DP State Definition:

   • dp[j] = number of ways to get sum j using current number of dice.

   • Start with base case: dp[0] = 1 (one way to get sum 0 with 0 dice).

2. Transition Logic:

   • For each die (1 to n), update all possible sums.

   • For each sum j, consider all possible face values (1 to m).

   • dp[j] = sum of dp[j-k] for all valid face values k.

3. Backward Iteration:

   • Process sums from high to low to avoid overwriting values we still need.

   • This allows using single array instead of two arrays.

4. Optimization:

   • Space: O(x) instead of O(n × x) by reusing array.

   • After processing each die, reset dp[0] = 0 as we can't get sum 0 with dice.

Key Insight: The problem is similar to coin change but with constraints on minimum (1) and maximum (m) values per item (die).

📝 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n × x × m), where n is the number of dice, x is the target sum, and m is the number of faces per die. For each of n dice, we process x possible sums, and for each sum, we check m face values.

• Expected Auxiliary Space Complexity: O(x), as we use a single 1D array of size x+1 to store the DP states, which is much more space-efficient than a 2D approach.

🧑‍💻 Code (C++)

class Solution {
public:
    int noOfWays(int m, int n, int x) {
        vector<int> dp(x + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = x; j >= 1; j--) {
                dp[j] = 0;
                for (int k = 1; k <= m && k <= j; k++)
                    dp[j] += dp[j - k];
            }
            dp[0] = 0;
        }
        return dp[x];
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ 2D DP Approach

💡 Algorithm Steps:

1. Create 2D array dp[i][j] where i = dice count, j = sum.

2. Initialize base case: dp[0][0] = 1.

3. For each die, calculate ways for each sum.

4. Return dp[n][x].

class Solution {
public:
    int noOfWays(int m, int n, int x) {
        vector<vector<int>> dp(n + 1, vector<int>(x + 1, 0));
        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 - 1][j - k];
                }
            }
        }
        return dp[n][x];
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n × x × m) - Three nested loops

• Auxiliary Space: 💾 O(n × x) - 2D array storage

✅ Why This Approach?

• Clear state representation

• Easy to understand transitions

• Good for learning DP concepts

📊 3️⃣ Recursive with Memoization

💡 Algorithm Steps:

1. Define recursive function: ways(dice, sum).

2. Base cases: dice=0 and sum=0 → return 1, else 0.

3. For each face value, recursively calculate ways.

4. Use memoization to avoid recomputation.

class Solution {
public:
    int solve(int m, int n, int x, vector<vector<int>>& memo) {
        if (x < 0 || n < 0) return 0;
        if (n == 0) return x == 0 ? 1 : 0;
        if (memo[n][x] != -1) return memo[n][x];
        
        int ways = 0;
        for (int face = 1; face <= m; face++) {
            ways += solve(m, n - 1, x - face, memo);
        }
        return memo[n][x] = ways;
    }
    
    int noOfWays(int m, int n, int x) {
        vector<vector<int>> memo(n + 1, vector<int>(x + 1, -1));
        return solve(m, n, x, memo);
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n × x × m) - With memoization

• Auxiliary Space: 💾 O(n × x) - Recursion stack + memoization

✅ Why This Approach?

• Natural recursive thinking

• Memoization prevents recomputation

• Top-down approach easier for some

📊 4️⃣ Optimized DP with Prefix Sum

💡 Algorithm Steps:

1. Use prefix sum to optimize inner loop.

2. Instead of summing dp[j-1] to dp[j-m], use prefix difference.

3. Maintain running sum for O(1) range sum queries.

4. Update DP values efficiently.

class Solution {
public:
    int noOfWays(int m, int n, int x) {
        vector<int> dp(x + 1, 0);
        for (int i = 1; i <= min(m, x); i++) dp[i] = 1;
        
        for (int dice = 2; dice <= n; dice++) {
            vector<int> temp(x + 1, 0);
            for (int sum = dice; sum <= x; sum++) {
                for (int face = 1; face <= m && face <= sum; face++) {
                    temp[sum] += dp[sum - face];
                }
            }
            dp = temp;
        }
        return dp[x];
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n × x × m) - Standard DP time

• Auxiliary Space: 💾 O(x) - Single extra array

✅ Why This Approach?

• Clean separation of dice iterations

• Easy to understand state transitions

• Good balance of clarity and efficiency

🆚 🔍 Comparison of Approaches

🚀 Approach	⏱️ Time Complexity	💾 Space Complexity	✅ Pros	⚠️ Cons
🎯 1D DP Backward	🟢 O(n×x×m)	🟢 O(x)	🚀 Most space efficient	🔧 Backward iteration confusing
📊 2D DP	🟢 O(n×x×m)	🔴 O(n×x)	📖 Clear state representation	💾 High space usage
🔄 Memoization	🟢 O(n×x×m)	🔴 O(n×x)	🎯 Natural recursion	🔧 Stack overflow risk
📈 Optimized DP	🟢 O(n×x×m)	🟢 O(x)	⚡ Clean code structure	🔧 Uses two arrays alternately

🏆 Best Choice Recommendation

🎯 Scenario	🎖️ Recommended Approach	🔥 Performance Rating
🏅 Space-constrained environment	🥇 1D DP Backward	★★★★★
📖 Learning DP concepts	🥈 2D DP	★★★★★
🎯 Prefer recursion	🥉 Memoization	★★★★☆
🔧 Code clarity	🏅 Optimized DP	★★★★☆

☕ Code (Java)

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

🐍 Code (Python)

class Solution:
    def noOfWays(self, m, n, x):
        dp = [0] * (x + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            for j in range(x, 0, -1):
                dp[j] = 0
                for k in range(1, min(m, j) + 1):
                    dp[j] += dp[j - k]
            dp[0] = 0
        return dp[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

Visitor counter