Domain 2MediumMEDIUM

Number of Dice Rolls With Target Sum

LeetCode problem 1155: Number of Dice Rolls With Target Sum (medium).

Domain: medium•Updated: 2026-09-09
#Dynamic Programming

Problem Breakdown

We are tasked with finding the number of distinct sequences of dice rolls that result in a specific target sum, given d dice where each die has faces numbered from 1 to f.

Key Inputs:

  • d: Number of dice (integers).
  • f: Faces per die (values 1…f1 \dots f).
  • target: The desired total sum.

Output: The count of valid combinations modulo 109+710^9 + 7.

Implicit Constraints & Edge Cases:

  • Impossible Sums: If the minimum possible sum (d×1d \times 1) exceeds target, or if the maximum possible sum (d×fd \times f) is less than target, the answer must be 0. The DP logic naturally handles this, but it’s good to keep in mind for early pruning (though not strictly necessary given constraints).
  • Overflow: Since we are counting combinations, the number can grow exponentially. We must apply modulo arithmetic at every addition step to prevent integer overflow and meet problem requirements.
  • Base Case: Before rolling any dice (d=0), there is exactly one way to have a sum of 0 (by doing nothing). This initializes our DP state correctly.

Intuition

A brute-force approach would involve generating all possible permutations of rolls (fdf^d) and checking their sums. With d,f≤30d, f \leq 30, this results in roughly 303030^{30} operations, which is computationally impossible (Time Limit Exceeded).

We need to build the solution incrementally using Dynamic Programming. The core insight is that we don’t care about which specific dice produced a sum; we only care about how many ways we can reach a certain sum after rolling ii dice.

Let dp[i][j] represent the number of ways to get a sum j using exactly i dice. To calculate this for die count i, we look at all possible outcomes from i-1 dice. If we had a valid way to reach sum prev_sum with i-1 dice, and we roll face value k on the current die (where 1≤k≤f1 \le k \le f), then we have reached sum new_sum = prev_sum + k.

This suggests an iterative approach where we update our state from 0 dice up to d dice. We can optimize space by only storing the previous row of sums, reducing memory usage significantly compared to a full O(d×target)O(d \times target) table.

Approach

  1. Initialize State: Create a DP array representing ways to achieve each sum using zero dice. The base case is dp[0] = 1 (sum 0 with 0 dice). All other sums are initially impossible (0).
  2. Iterate Dice Count: Loop from 1 to d. In each iteration, we simulate rolling one more die.
  3. Transition Logic: For the current number of dice rolled so far, iterate through all possible previous sums that were achievable (where count > 0). For every valid face value kk (1…f1 \dots f), add the ways from dp[prev_sum] to a new state at index prev_sum + k.
  4. Modulo Arithmetic: Apply modulo 109+710^9 + 7 after each addition to keep numbers manageable and correct per requirements.
  5. Update State: Replace the old DP array with the newly computed one for the current die count before moving to the next iteration (Rolling Array technique).

Complexity Analysis

  • Time Complexity: O(d⋅f⋅target)O(d \cdot f \cdot target).
    • We iterate d times.
    • For each die, we potentially update sums up to target.
    • Each state transition considers f faces.
    • Given constraints (30×6×100030 \times 6 \times 1000), this is roughly 180,000180,000 operations per test case, which fits comfortably within standard time limits (usually ∼107−108\sim 10^7-10^8 ops/sec).
  • Space Complexity: O(target)O(target).
    • We use two arrays of size target + 1 to store the current and previous states. This is significantly more efficient than a full table, though given constraints (d≤30d \leq 30, target ≤1000\leq 1000), even an O(d⋅target)O(d \cdot target) space solution would pass easily.

Solution

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        MOD = 10**9 + 7
        
        # dp[j] will store the number of ways to get sum 'j' with current dice count.
        # Initialize for 0 dice: only sum 0 is possible (1 way).
        dp = [0] * (target + 1)
        dp[0] = 1
        
        # Iterate through each die from 1 to d
        for _ in range(d):
            new_dp = [0] * (target + 1)
            
            # We iterate over all possible sums achievable with previous dice.
            # Optimization: Only check indices where dp[s] > 0, but iterating 
            # the full range is cleaner and fast enough given constraints.
            for s in range(target + 1):
                if dp[s] == 0:
                    continue
                
                # Try rolling each face value k from current die (1 to f)
                for k in range(1, f + 1):
                    new_sum = s + k
                    if new_sum <= target:
                        new_dp[new_sum] += dp[s]
            
            # Update DP table and apply modulo at the end of each dice iteration 
            # (or during addition to keep numbers smaller). Here we do it after update.
            for i in range(target + 1):
                if new_dp[i]:
                    new_dp[i] %= MOD
            
            dp = new_dp
        
        return dp[target] % MOD

Edge Cases Handled

  • Unreachable Target: If target is larger than the maximum possible sum (d×fd \times f), or smaller than minimum (d×1d \times 1), the DP array will naturally result in 0 for that index.
  • Zero Base Case: The initialization dp[0] = 1 correctly handles the mathematical identity element required to propagate counts forward through subsequent dice rolls.
  • Modulo Overflow: By applying % MOD at each addition step (or after accumulation), we ensure values stay within standard integer limits and satisfy the problem’s requirement for modulo arithmetic, preventing potential overflow issues in languages with fixed-size integers (though Python handles large ints automatically).