Number of Dice Rolls With Target Sum
Number of Dice Rolls With Target Sum is a medium dynamic programming problem solved with the 2d dp pattern.
The best approach, optimal (bottom-up dp with a sliding-window sum), runs in O(n · target) time and O(target) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every face recursively) up.
Problem
You roll n dice, and each die has k faces numbered 1 to k. A roll is the ordered list of the values shown by all n dice, so showing (1, 2) and (2, 1) counts as two different rolls.
Return how many of the k^n possible rolls have values that add up to exactly target. The count can be very large, so return it modulo 10^9 + 7.
Examples
Example 1
- Input
n = 2, k = 4, target = 5- Output
4- Why
- With two four-sided dice the ordered rolls (1,4), (2,3), (3,2) and (4,1) add up to 5.
Example 2
- Input
n = 3, k = 2, target = 4- Output
3- Why
- Each die shows 1 or 2, so exactly one die must show 2: it can be the first, second or third die.
Example 3
- Input
n = 1, k = 5, target = 7- Output
0- Why
- A single die with faces 1 to 5 can never show 7.
Constraints
1 <= n, k <= 301 <= target <= 1000- Return the count modulo
10^9 + 7.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every face recursively) | O(k^n) | O(n) |
| Better (memoized recursion) | O(n · target · k) | O(n · target) |
| Optimal (bottom-up DP with a sliding-window sum) | O(n · target) | O(target) |
1Brute force (try every face recursively)
O(k^n)Each level branches up to k ways and there are n levels.O(n)Only the recursion stack, n frames deep.count(dice, sum) tries every face f of the next die from 1 to k (as long as f does not exceed the remaining sum) and adds count(dice - 1, sum - f). With no dice left, the roll counts only if the remaining sum is exactly 0.
- count(0, s) = 1 if s == 0 else 0.
- count(d, s) = Σ count(d - 1, s - f) for f = 1 .. min(k, s), taken modulo 10^9 + 7.
class Solution {
private static final int MOD = 1_000_000_007;
public int numRollsToTarget(int n, int k, int target) {
return count(n, k, target);
}
private int count(int dice, int k, int sum) {
if (dice == 0) return sum == 0 ? 1 : 0;
long total = 0;
for (int f = 1; f <= k && f <= sum; f++) {
total += count(dice - 1, k, sum - f);
}
return (int) (total % MOD);
}
}class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
def count(dice: int, total: int) -> int:
if dice == 0:
return 1 if total == 0 else 0
ways = 0
for f in range(1, min(k, total) + 1):
ways += count(dice - 1, total - f)
return ways % MOD
return count(n, target)class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
return count(n, k, target);
}
private:
static const int MOD = 1000000007;
int count(int dice, int k, int sum) {
if (dice == 0) return sum == 0 ? 1 : 0;
long long total = 0;
for (int f = 1; f <= k && f <= sum; f++) {
total += count(dice - 1, k, sum - f);
}
return (int)(total % MOD);
}
};function numRollsToTarget(n, k, target) {
const MOD = 1000000007;
const count = (dice, sum) => {
if (dice === 0) return sum === 0 ? 1 : 0;
let total = 0;
for (let f = 1; f <= k && f <= sum; f++) {
total += count(dice - 1, sum - f);
}
return total % MOD;
};
return count(n, target);
}2Better (memoized recursion)
O(n · target · k)Each of the n · target states loops over up to k faces once.O(n · target)The memo table, plus n frames of recursion.The recursion above recomputes the same (dice, sum) states again and again. There are only (n + 1) · (target + 1) distinct states, so caching each result turns the exponential search into a table fill.
- memo[d][s] = -1 initially.
- count(d, s): base case as before; if memo[d][s] is set, return it.
- Otherwise sum count(d - 1, s - f) for f = 1 .. min(k, s), store modulo 10^9 + 7 and return.
class Solution {
private static final int MOD = 1_000_000_007;
private int[][] memo;
public int numRollsToTarget(int n, int k, int target) {
memo = new int[n + 1][target + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return count(n, k, target);
}
private int count(int dice, int k, int sum) {
if (dice == 0) return sum == 0 ? 1 : 0;
if (memo[dice][sum] != -1) return memo[dice][sum];
long total = 0;
for (int f = 1; f <= k && f <= sum; f++) {
total += count(dice - 1, k, sum - f);
}
memo[dice][sum] = (int) (total % MOD);
return memo[dice][sum];
}
}class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
memo = [[-1] * (target + 1) for _ in range(n + 1)]
def count(dice: int, total: int) -> int:
if dice == 0:
return 1 if total == 0 else 0
if memo[dice][total] != -1:
return memo[dice][total]
ways = 0
for f in range(1, min(k, total) + 1):
ways += count(dice - 1, total - f)
memo[dice][total] = ways % MOD
return memo[dice][total]
return count(n, target)class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
memo.assign(n + 1, vector<int>(target + 1, -1));
return count(n, k, target);
}
private:
static const int MOD = 1000000007;
vector<vector<int>> memo;
int count(int dice, int k, int sum) {
if (dice == 0) return sum == 0 ? 1 : 0;
if (memo[dice][sum] != -1) return memo[dice][sum];
long long total = 0;
for (int f = 1; f <= k && f <= sum; f++) {
total += count(dice - 1, k, sum - f);
}
return memo[dice][sum] = (int)(total % MOD);
}
};function numRollsToTarget(n, k, target) {
const MOD = 1000000007;
const memo = Array.from({ length: n + 1 }, () => new Array(target + 1).fill(-1));
const count = (dice, sum) => {
if (dice === 0) return sum === 0 ? 1 : 0;
if (memo[dice][sum] !== -1) return memo[dice][sum];
let total = 0;
for (let f = 1; f <= k && f <= sum; f++) {
total += count(dice - 1, sum - f);
}
memo[dice][sum] = total % MOD;
return memo[dice][sum];
};
return count(n, target);
}3Optimal (bottom-up DP with a sliding-window sum)
O(n · target)n rows, each filled in one left-to-right pass with constant work per cell.O(target)Two arrays of length target + 1.Build the counts one die at a time. With i dice, the number of ways to reach sum s is the sum of the previous row over s-1 down to s-k. Moving s one step to the right adds dp[s-1] to that window and drops dp[s-k-1], so each cell takes O(1) and only two rows of length target + 1 are kept.
- dp[0] = 1 (zero dice make sum 0); all other entries 0.
- Repeat n times: next[0] = 0; window = 0; for s = 1 .. target: window += dp[s-1]; if s-k-1 >= 0, window -= dp[s-k-1]; next[s] = window mod 10^9 + 7.
- dp = next. Return dp[target].
class Solution {
public int numRollsToTarget(int n, int k, int target) {
final long MOD = 1_000_000_007L;
long[] dp = new long[target + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
long[] next = new long[target + 1];
long window = 0;
for (int s = 1; s <= target; s++) {
window += dp[s - 1];
if (s - k - 1 >= 0) window -= dp[s - k - 1];
window = ((window % MOD) + MOD) % MOD;
next[s] = window;
}
dp = next;
}
return (int) dp[target];
}
}class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
dp = [0] * (target + 1)
dp[0] = 1
for _ in range(n):
nxt = [0] * (target + 1)
window = 0
for s in range(1, target + 1):
window += dp[s - 1]
if s - k - 1 >= 0:
window -= dp[s - k - 1]
window %= MOD
nxt[s] = window
dp = nxt
return dp[target]class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
const long long MOD = 1000000007LL;
vector<long long> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
vector<long long> next(target + 1, 0);
long long window = 0;
for (int s = 1; s <= target; s++) {
window += dp[s - 1];
if (s - k - 1 >= 0) window -= dp[s - k - 1];
window = ((window % MOD) + MOD) % MOD;
next[s] = window;
}
dp = next;
}
return (int)dp[target];
}
};function numRollsToTarget(n, k, target) {
const MOD = 1000000007;
let dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= n; i++) {
const next = new Array(target + 1).fill(0);
let window = 0;
for (let s = 1; s <= target; s++) {
window += dp[s - 1];
if (s - k - 1 >= 0) window -= dp[s - k - 1];
window = ((window % MOD) + MOD) % MOD;
next[s] = window;
}
dp = next;
}
return dp[target];
}Edge cases to test
- target smaller than n (every die shows at least 1, answer 0)
- target larger than n · k (answer 0)
- target exactly n or exactly n · k (answer 1)
- k = 1 (only one possible roll)
- Large n and k, where the count overflows 32-bit integers without the modulus
Hints
Hint 1
Fix the value of the first die. The remaining n - 1 dice must then add up to target minus that value.
Hint 2
The same (dice left, sum left) pair is reached by many different prefixes. Cache it.
Hint 3
Bottom-up: ways[i][s] = ways[i-1][s-1] + … + ways[i-1][s-k]. That sum is a sliding window over the previous row, so each cell costs O(1).
FAQ
What is the best time complexity for Number of Dice Rolls With Target Sum?
Optimal (bottom-up DP with a sliding-window sum) runs in O(n · target) time and O(target) extra space. n rows, each filled in one left-to-right pass with constant work per cell.
Which pattern does Number of Dice Rolls With Target Sum use?
It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.
Is there a brute force solution for Number of Dice Rolls With Target Sum?
Yes. Brute force (try every face recursively) takes O(k^n) time and O(n) space. count(dice, sum) tries every face f of the next die from 1 to k (as long as f does not exceed the remaining sum) and adds count(dice - 1, sum - f).
Which edge cases should I test for Number of Dice Rolls With Target Sum?
target smaller than n (every die shows at least 1, answer 0); target larger than n · k (answer 0); target exactly n or exactly n · k (answer 1); k = 1 (only one possible roll); Large n and k, where the count overflows 32-bit integers without the modulus.