Number of Dice Rolls With Target Sum: Coding Problem Solution

Number of Dice Rolls With Target Sum

Number of Dice Rolls With Target Sum is a dynamic programming problem that asks you to count how many different ways you can reach an exact total using dice rolls. You are given three integers: the number of dice n, the number of faces per die k, and a target sum.

Each die produces a value between 1 and k. You roll all n dice once, add the outcomes, and want the total to equal the target. Your job is to compute how many distinct sequences of outcomes produce that exact sum.

This is a counting problem, not an optimization problem. You are not asked for the minimum or maximum number of rolls. You are asked for the total number of valid ways, which can grow extremely large. Because of that, the problem typically requires returning the answer modulo a large number (commonly 1,000,000,007) to keep values manageable.

Interviewers like this problem because it checks whether you can build a correct DP state, handle constraints cleanly, and avoid exponential explosion from naive recursion.

Why brute force fails quickly

A direct approach would try all possibilities for each die. With k possible outcomes per die and n dice, there are k^n sequences to consider. Even with moderate values, that becomes too large.

Recursion without memoization will repeat the same subproblems many times. For example, the number of ways to reach sum 7 with 3 dice will be computed over and over while exploring different paths.

This is exactly the kind of structure dynamic programming is meant to handle.

Want to explore more coding problem solutions? Check out the Delete Node in a Linked List and Merge Two Binary Trees.

The core idea behind the solution

The solution is built around a simple question:

How many ways are there to reach a sum s using exactly d dice?

Once you can answer that for smaller values of d and s, you can build up to the final answer for n dice and the target sum.

This naturally leads to a DP table where rows represent the number of dice used, and columns represent the running sum.

How the recurrence works

To compute the number of ways to reach a sum s with d dice, you consider what the last die could have rolled.

If the last die shows a value x between 1 and k, then the first d - 1 dice must sum to s - x.

So the number of ways to reach (d, s) is the sum of the number of ways to reach (d - 1, s - 1), (d - 1, s - 2), and so on up to (d - 1, s - k), as long as those sums are valid.

This recurrence captures the full counting logic. Every valid full sequence ends with some last roll, and you count all the ways that lead into it.

The base case that anchors the DP

The most important starting point is that there is exactly one way to reach sum 0 with 0 dice: do nothing.

That becomes the foundation from which all other states are built.

From there, the DP will correctly compute ways for 1 die, then 2 dice, and so on, until you reach n dice.

Handling impossible sums early

A helpful way to reason about correctness is to notice the natural bounds.

With d dice, the minimum possible sum is d (all ones), and the maximum possible sum is d * k (all ks). Any sum outside that range has zero ways.

A clean implementation uses these bounds to skip unnecessary work and avoid negative indices.

Even conceptually, these constraints explain why the DP table does not need to compute every sum for every dice count.

Why modulo arithmetic is required

The number of combinations grows rapidly. Even for relatively small n and k, the count can exceed typical integer limits.

That’s why the result is taken modulo a large prime. Applying the modulo during DP updates ensures numbers remain safe and operations stay fast.

Performance in simple terms

The DP approach runs in time proportional to the number of dice multiplied by the target sum and the number of faces, because each state may sum over up to k previous states.

Space can be kept reasonable by only storing the previous row (for d - 1 dice) while computing the current row (for d dice), since the recurrence only depends on the immediate previous dice count.

This is a standard optimization that keeps the solution efficient.