Dice Throws

Tags

Dice Throws

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given n dice, each with f faces (numbered 1 to f), compute the number of ways to roll the dice so that the sum of the face values equals a given target.

Intuition

Each die contributes a value between 1 and f. The total number of ways to reach a target sum with n dice decomposes naturally: for the last die showing face value v, the remaining n-1 dice must sum to target - v. This recursive structure with overlapping subproblems (many combinations of dice count and remaining sum repeat) makes it ideal for dynamic programming.

Approach

  1. Create a 2D table dp of size (n+1) x (target+1), where dp[d][t] is the number of ways to get sum t using d dice.
  2. Base case: dp[0][0] = 1 (zero dice, zero sum: one way — do nothing).
  3. For each die d from 1 to n:
    • For each sum t from 0 to target:
      • For each face v from 1 to f:
        • If t - v >= 0: dp[d][t] += dp[d-1][t-v]
  4. Return dp[n][target].

Pseudocode

function diceThrows(n, f, target):
    dp = 2D array of size (n+1) x (target+1), filled with 0
    dp[0][0] = 1

    for d from 1 to n:
        for t from 1 to target:
            for v from 1 to f:
                if t - v >= 0:
                    dp[d][t] += dp[d-1][t-v]

    return dp[n][target]

Time & Space Complexity

MeasureComplexityJustification
TimeO(n * target * f)Three nested loops over dice, target sums, and face values
SpaceO(n * target)DP table; reducible to O(target) using rolling array since each row depends only on the previous row

Key Insights

  • The inner loop over face values is essentially a bounded sliding window sum on the previous row. This can be optimized with a prefix sum to eliminate the face-value loop, reducing time to O(n * target).
  • The base case dp[0][0] = 1 is critical: it represents the "empty product" — zero dice sum to zero in exactly one way.
  • If the target is less than n (minimum possible sum with all 1s) or greater than n * f (maximum possible sum), the answer is immediately 0.
  • This problem is a restricted variant of the coin change count problem, where each "coin" (face value) must be used exactly n times total (once per die).

Edge Cases

  • Target is 0 with n > 0: impossible since each die contributes at least 1; answer is 0.
  • n = 0 and target = 0: answer is 1 (base case).
  • Target < n or target > n * f: answer is 0; these sums are unreachable.
  • f = 1: every die shows 1, so the only achievable sum is n; answer is 1 if target == n, else 0.
  • n = 1: each face value from 1 to min(f, target) contributes exactly one way.

Linked mentions