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 tom
,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:
Create a 2D vector
dp[n+1][x+1]
and initializedp[0][0] = 1
.Loop
i
from1
ton
(number of dice).Loop
j
from1
tox
(target sum).For each
k
from1
tom
, ifj โฅ k
, adddp[i-1][j-k]
todp[i][j]
.Return
dp[n][x]
.
๐งฎ Time and Auxiliary Space Complexity
Time Complexity: O(n ร x ร m) We compute each state
(i, j)
using up tom
previous states.Auxiliary Space Complexity: O(n ร x) We use a 2D DP table with
n+1
rows andx+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];
}
};
๐งโ๐ป 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