LeetCode 1155 - Number of Dice Rolls With Target Sum

The problem gives us n identical dice, where each die has faces numbered from 1 to k. We roll all n dice and want to count how many different sequences of rolls produce a total sum equal to target. The important detail is that order matters.

leetcodemediumdynamic-programming

LeetCode Problem 1155

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem gives us n identical dice, where each die has faces numbered from 1 to k. We roll all n dice and want to count how many different sequences of rolls produce a total sum equal to target.

The important detail is that order matters. For example, when rolling two six-sided dice and targeting a sum of 7, the outcomes (1, 6) and (6, 1) are considered different ways. We are not counting combinations, we are counting ordered sequences of dice rolls.

The input consists of:

  • n, the number of dice
  • k, the number of faces on each die
  • target, the desired total sum

The output should be the total number of valid roll sequences whose values add up to target.

Since the number of possible outcomes can become extremely large, the answer must be returned modulo 10^9 + 7. This is a common requirement in combinatorics and dynamic programming problems to prevent integer overflow and keep values manageable.

The constraints are important:

  • 1 <= n, k <= 30
  • 1 <= target <= 1000

A naive solution would try every possible sequence of rolls. Since each die has k choices, the total number of sequences is k^n. In the worst case, that becomes 30^30, which is astronomically large and completely infeasible.

The constraints strongly suggest that we need a dynamic programming solution.

Several edge cases are important:

  • The target may be impossible to achieve. For example, with n = 2, the minimum sum is 2 and the maximum sum is 2 * k. Any target outside this range should return 0.
  • A target equal to the minimum or maximum possible sum often has only one valid arrangement.
  • Large values of n, k, and target require careful optimization to avoid excessive runtime.
  • Intermediate counts become very large, so modulo arithmetic must be applied consistently.

Approaches

Brute Force Approach

The most direct solution is to generate every possible sequence of dice rolls and count how many sequences sum to target.

We can think of this as a recursive search:

  • For each die, try every face value from 1 to k
  • Track the running sum
  • Once all n dice are used, check whether the sum equals target

This approach is correct because it explicitly explores every valid sequence of rolls and counts exactly those whose total matches the target.

However, the runtime is terrible. Each die introduces k branching choices, so the total number of recursive paths is k^n.

For the maximum constraints:

$$30^{30}$$

This is completely impractical.

Optimal Dynamic Programming Approach

The key observation is that many subproblems repeat.

Suppose we already know:

  • how many ways there are to make sum s
  • using exactly d dice

Then, to compute the number of ways to make a larger sum with one more die, we can extend those previous results.

This naturally leads to dynamic programming.

We define:

$$dp[d][s]$$

as the number of ways to achieve sum s using exactly d dice.

To compute this:

  • Try every possible face value from 1 to k
  • If the current die shows face, then the previous dice must have formed:

$$s - face$$

So the recurrence becomes:

$dp[d][s]=\sum_{face=1}^{k} dp[d-1][s-face]$

This avoids recomputing the same states repeatedly.

Because each state depends only on the previous row, we can optimize space from a full 2D table down to two 1D arrays.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k^n) O(n) Tries every possible roll sequence recursively
Optimal Dynamic Programming O(n * target * k) O(target) Builds solutions incrementally using previous states

Algorithm Walkthrough

  1. Create a constant MOD = 10^9 + 7.

The number of possible roll sequences grows very quickly, so every addition must be taken modulo MOD. 2. Initialize a DP array.

We use a 1D array dp where:

$$dp[s]$$

represents the number of ways to create sum s using the current number of processed dice. 3. Set the base case.

Before rolling any dice, there is exactly one way to create sum 0:

$dp[0]=1$

Every other sum initially has 0 ways.

  1. Process dice one at a time.

For each die:

  • Create a fresh array next_dp
  • This array will store results for the new number of dice
  1. For every possible current sum:

If dp[current_sum] is nonzero, try every face value from 1 to k. 3. Update the next state.

If the current die shows face, then the new sum becomes:

$new_sum=current_sum+face$

Add the number of ways from the previous state:

$next_dp[new_sum]+=dp[current_sum]$

Apply modulo after every addition.

  1. Replace the old DP array.

After processing all sums and face values for the current die, assign:

dp = next_dp
  1. Return the result.

After all n dice are processed, the answer is:

dp[target]

Why it works

The algorithm works because every valid sequence of dice rolls can be constructed incrementally.

For each die, we consider all possible face values and extend all previously reachable sums. Since every state represents the exact number of ways to form a sum with a fixed number of dice, and every transition corresponds to adding one legal die value, the DP table counts every valid sequence exactly once.

Python Solution

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7

        # Impossible target
        if target < n or target > n * k:
            return 0

        dp = [0] * (target + 1)
        dp[0] = 1

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

            for current_sum in range(target + 1):
                if dp[current_sum] == 0:
                    continue

                for face in range(1, k + 1):
                    new_sum = current_sum + face

                    if new_sum > target:
                        break

                    next_dp[new_sum] = (
                        next_dp[new_sum] + dp[current_sum]
                    ) % MOD

            dp = next_dp

        return dp[target]

The implementation begins with an early impossibility check. If the target is smaller than the minimum achievable sum or larger than the maximum achievable sum, the function immediately returns 0.

The dp array stores the number of ways to form each sum using the dice processed so far. Initially, only sum 0 is possible with zero dice.

For each die, a new array next_dp is created. This prevents overwriting states that are still needed for the current iteration.

The nested loops iterate through:

  • every currently reachable sum
  • every possible face value

Whenever a new valid sum is formed, the count is accumulated into next_dp.

Modulo arithmetic is applied immediately after addition to keep numbers bounded.

At the end of each die iteration, dp is replaced with next_dp, advancing the DP state forward.

Go Solution

func numRollsToTarget(n int, k int, target int) int {
	const MOD int = 1000000007

	// Impossible target
	if target < n || target > n*k {
		return 0
	}

	dp := make([]int, target+1)
	dp[0] = 1

	for dice := 0; dice < n; dice++ {
		nextDP := make([]int, target+1)

		for currentSum := 0; currentSum <= target; currentSum++ {
			if dp[currentSum] == 0 {
				continue
			}

			for face := 1; face <= k; face++ {
				newSum := currentSum + face

				if newSum > target {
					break
				}

				nextDP[newSum] =
					(nextDP[newSum] + dp[currentSum]) % MOD
			}
		}

		dp = nextDP
	}

	return dp[target]
}

The Go implementation follows the exact same dynamic programming logic as the Python version.

Slices are used instead of Python lists. Since Go integers are fixed-width, modulo arithmetic is especially important to avoid overflow during accumulation.

Unlike Python, Go does not support arbitrary precision integers by default, so using modulo throughout the computation is essential.

Worked Examples

Example 1

Input:

n = 1
k = 6
target = 3

Initial state:

Sum Ways
0 1

After processing one die:

Face New Sum Ways
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
6 6 1

Final DP state:

Sum Ways
0 0
1 1
2 1
3 1

Answer:

1

Example 2

Input:

n = 2
k = 6
target = 7

Initial state:

Sum Ways
0 1

After first die:

Sum Ways
1 1
2 1
3 1
4 1
5 1
6 1

After second die:

Previous Sum Face New Sum
1 6 7
2 5 7
3 4 7
4 3 7
5 2 7
6 1 7

Total ways for sum 7:

Sum Ways
7 6

Answer:

6

Example 3

Input:

n = 30
k = 30
target = 500

The DP table becomes very large, so only conceptual progression is shown.

The algorithm repeatedly builds:

  • ways to form sums with 1 die
  • then 2 dice
  • then 3 dice
  • continuing until 30 dice

Each state aggregates all legal previous sums.

Final result:

222616187

This value is already reduced modulo:

$10^9+7$

Complexity Analysis

Measure Complexity Explanation
Time O(n * target * k) For every die, iterate through all target sums and all face values
Space O(target) Only two 1D DP arrays are stored

The runtime comes from three nested loops:

  • one loop over dice
  • one loop over target sums
  • one loop over face values

Given the constraints:

$$30 \times 1000 \times 30 = 900000$$

This is efficient enough.

Space optimization is possible because each DP row depends only on the previous row, not the entire table.

Test Cases

solution = Solution()

# Provided examples
assert solution.numRollsToTarget(1, 6, 3) == 1  # Single die exact match
assert solution.numRollsToTarget(2, 6, 7) == 6  # Standard two-dice combinations
assert solution.numRollsToTarget(30, 30, 500) == 222616187  # Large constraints

# Minimum constraints
assert solution.numRollsToTarget(1, 1, 1) == 1  # Only one possible roll

# Impossible targets
assert solution.numRollsToTarget(2, 6, 1) == 0  # Smaller than minimum sum
assert solution.numRollsToTarget(2, 6, 13) == 0  # Larger than maximum sum

# Exact minimum sum
assert solution.numRollsToTarget(3, 6, 3) == 1  # All dice must be 1

# Exact maximum sum
assert solution.numRollsToTarget(3, 6, 18) == 1  # All dice must be 6

# Small combinational checks
assert solution.numRollsToTarget(2, 2, 2) == 1  # (1,1)
assert solution.numRollsToTarget(2, 2, 3) == 2  # (1,2), (2,1)
assert solution.numRollsToTarget(2, 2, 4) == 1  # (2,2)

# Medium-sized validation
assert solution.numRollsToTarget(3, 4, 5) == 6  # Multiple valid arrangements

# Stress-style cases
assert solution.numRollsToTarget(10, 6, 30) > 0  # Larger DP state
assert solution.numRollsToTarget(20, 10, 100) > 0  # Large but feasible

Test Summary

Test Why
(1, 6, 3) Verifies basic single-die behavior
(2, 6, 7) Validates multiple ordered combinations
(30, 30, 500) Tests large-scale DP performance
(1, 1, 1) Smallest valid input
(2, 6, 1) Impossible low target
(2, 6, 13) Impossible high target
(3, 6, 3) Minimum achievable sum
(3, 6, 18) Maximum achievable sum
(2, 2, 2) Single valid arrangement
(2, 2, 3) Multiple ordered arrangements
(2, 2, 4) Single maximum arrangement
(3, 4, 5) Medium combinational validation
(10, 6, 30) Larger DP coverage
(20, 10, 100) Stress-style performance test

Edge Cases

One important edge case occurs when the target is smaller than the minimum achievable sum. Since each die contributes at least 1, the minimum possible total with n dice is n. If target < n, there are no valid roll sequences. The implementation handles this immediately with an early return.

Another important edge case occurs when the target exceeds the maximum achievable sum. Since each die contributes at most k, the largest possible total is n * k. Any target larger than this is impossible. Without this check, the algorithm would still run correctly, but it would waste time processing states that can never be reached.

A third important edge case involves sums at the boundaries of possibility. For example, when the target equals the minimum possible sum, there is exactly one valid arrangement: every die must show 1. Similarly, when the target equals the maximum possible sum, every die must show k. These cases can expose indexing or transition bugs in DP implementations, but the recurrence naturally handles them correctly.

Another subtle edge case involves large intermediate counts. Even when the final answer fits inside normal integer ranges after modulo reduction, intermediate values can become enormous. Applying modulo during every update prevents overflow and keeps computation efficient.

Finally, careful handling of DP state updates is critical. Reusing the same array during iteration would accidentally mix states from the current and previous dice counts. Using a separate next_dp array guarantees that every transition uses only results from the previous layer of the dynamic programming process.