#1155

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Dice Rolls With Target Sum

Calculate the number of ways to roll n dice with k faces to reach a target sum using state transition dynamic programming.

dynamic programming

Problem Statement

You are given n dice, each with k faces numbered from 1 to k. Your task is to find how many possible ways the dice can be rolled so that the sum of all face-up numbers equals a specific target. The result should be returned modulo 10^9 + 7 because the number of combinations can be very large.

For example, with n = 2, k = 6, and target = 7, there are six sequences that produce the target sum: (1,6), (2,5), (3,4), (4,3), (5,2), and (6,1). Constraints are 1 <= n, k <= 30 and 1 <= target <= 1000, requiring an optimized state transition dynamic programming solution rather than brute-force enumeration.

Examples

Example 1

Input: n = 1, k = 6, target = 3

Output: 1

You throw one die with 6 faces. There is only one way to get a sum of 3.

Example 2

Input: n = 2, k = 6, target = 7

Output: 6

You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3

Input: n = 30, k = 30, target = 500

Output: 222616187

The answer must be returned modulo 109 + 7.

Constraints

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

Solution Approach

Define DP States

Use a 2D dynamic programming table dp[d][s] representing the number of ways to achieve sum s using d remaining dice. Initialize dp[0][0] = 1 and all other states as 0. This captures the essence of state transition dynamic programming for counting sequences.

Transition Between States

For each remaining dice d and for each sum s achievable so far, iterate over all possible face values f from 1 to k and update dp[d+1][s+f] += dp[d][s]. Each transition correctly propagates the count of sequences, reflecting the pattern of state transition dynamic programming and avoiding overcounting.

Modulo and Result Extraction

Since numbers grow large, take modulo 10^9 + 7 at every state update. After processing all dice, dp[n][target] contains the number of valid sequences. This ensures correctness and prevents integer overflow, which is a common failure mode if modulo handling is omitted.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * target * k) because for each of n dice and each intermediate sum up to target, we iterate over k faces. Space complexity is O(n * target) for the DP table, which can be optimized to O(target) using rolling arrays.

What Interviewers Usually Probe

The candidate should recognize the state definition as remaining dice and current sum.
The interviewer may check whether the solution handles large numbers with modulo 10^9 + 7.
Expect discussion of DP optimization to reduce space using a rolling array for sums.

Common Pitfalls or Variants

Common pitfalls

Forgetting to apply modulo at each update, causing integer overflow.
Incorrectly defining the DP state or transitions, leading to overcounting or missed sequences.
Attempting brute-force recursion without memoization, which exceeds time limits.

Follow-up variants

Count sequences where dice have non-uniform faces or different ranges.
Find the probability of rolling a sum rather than counting sequences.
Determine the minimum number of dice needed to reach at least the target sum.

FAQ

What pattern does Number of Dice Rolls With Target Sum follow?

It follows a state transition dynamic programming pattern where states track remaining dice and current sum.

Can this problem be solved with recursion alone?

Recursion without memoization is inefficient and may exceed time limits; memoized DP or iterative DP is recommended.

Why do we use modulo 10^9 + 7 in this problem?

Because the total number of sequences grows exponentially, modulo prevents integer overflow and keeps results within limits.

How can space complexity be optimized?

Use a rolling array to store only the current and previous dice states, reducing space from O(n * target) to O(target).

Is it necessary to iterate over all face values for each dice?

Yes, iterating over 1 to k for each dice ensures all valid sequences are counted according to state transition DP.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the number of ways to get a sum of $j$ using $i$ dice. Then, we can obtain the following state transition equation:

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1
        mod = 10**9 + 7
        for i in range(1, n + 1):
            for j in range(1, min(i * k, target) + 1):
                for h in range(1, min(j, k) + 1):
                    f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod
        return f[n][target]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1
        mod = 10**9 + 7
        for i in range(1, n + 1):
            for j in range(1, min(i * k, target) + 1):
                for h in range(1, min(j, k) + 1):
                    f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod
        return f[n][target]

Continue Practicing

#1162 as far from land as possible #1147 longest chunked palindrome decomposition #1143 longest common subsequence