Number of Dice Rolls with Target Sum

01-26-2026

Problem Statement

You have n dice, and each dice 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 $10^9 + 7$

Solution

At face value, it appears that the hard part of this problem is just permuting every single way to get to the target value. At first, you may think that you could isolate certain trees of values that add up to a target and then permute these trees and return the summation of that. While that would work, it is overly complicated and you would struggle with how to deal with duplicates. Alternatively, we can consider DP with counting. Similar to Coin Change 2, we can increment results from previous results until we get target.

So, conceptually, what do we need for this. Well, for every dice roll that lands on value i, we can look back and add s-i where s is the current sum to the current state. This leads us to the next question: what is the current state? To clearly represent where we are, we must have two states: the number of dice rolled d and the current sum s. This follows basic Knapsack DP principles/structure, looking something like this:

python

dp = [[0] * (target + 1) for _ in range(n+1)]

for d in dice:
	for s in range(1, target+1):

What this does is it inherently keeps track of the bounded capacity of the items, the dice in this case while being able to find every possibility to find every value in the range $[1\dots target]$ . We're still missing one last thing thing however... the actual dice value roll. This is simpe and requires just another loop to be added.

python

for d in dice:
	for s in range(1, target+1):	
		for i in range(1, k):

Putting it all together with our recurrence relation above:

python

MOD = 10**9 + 7

# dp[d][s] = number of ways to get sum s using d dice
dp = [[0] * (target + 1) for _ in range(n + 1)]

dp[0][0] = 1

for d in range(1, n + 1):
	for s in range(1, target + 1):
		for face in range(1, k + 1):
			if s - face >= 0:
				dp[d][s] = (dp[d][s] + dp[d - 1][s - face]) % MOD

return dp[n][target]

Runtime Complexity: O(n * target)
Space Complexity: O(n * target)