Number of Dice Rolls With Target Sum: DP on Dice

You have n dice, and each die has k faces numbered 1 to k. Given a target number, return the number of possible ways to roll the dice so that the sum of the face-up numbers equals target. Since the answer may be very large, return it modulo 10^9 + 7.

This is LeetCode 1155: Number of Dice Rolls With Target Sum, and it is one of the cleanest problems for learning the counting DP pattern. The structure it teaches shows up whenever you need to count combinations with a fixed number of bounded choices.

Why this problem matters

Counting the number of ways to reach a target using a fixed number of bounded choices is a pattern that appears constantly in dynamic programming. This problem is a textbook version of it: you have n stages (one per die), each stage contributes a value between 1 and k, and you want to know how many sequences of choices sum to a specific target.

The same structure shows up in bounded knapsack problems, probability calculations, and any scenario where you pick from a menu of options a fixed number of times and care about the total. Master the recurrence here, and you have a template for all of them.

The key insight

Define dp[i][j] as the number of ways to reach sum j using exactly i dice. The base case is dp[0][0] = 1: there is exactly one way to reach sum 0 with zero dice (roll nothing).

For each additional die, you choose a face value f from 1 to k. If the previous i - 1 dice summed to j - f, then adding face f gives sum j. So the recurrence is:

dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-k]

for all valid values where j - f >= 0. You fill the table row by row, from dice 1 up to dice n. The answer is dp[n][target].

The solution

def num_rolls_to_target(n: int, k: int, target: int) -> int:
    MOD = 10**9 + 7
    dp = [[0] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        for j in range(1, target + 1):
            for f in range(1, k + 1):
                if j - f >= 0:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - f]) % MOD

    return dp[n][target]

Let's walk through what each piece does.

The dp table has n + 1 rows (one per dice count, from 0 to n) and target + 1 columns (one per possible sum, from 0 to target). We initialize dp[0][0] = 1 because zero dice can only produce a sum of zero, and there is exactly one way to do that.

The outer loop iterates over dice count i from 1 to n. For each die, we consider every possible sum j. The innermost loop tries every face value f from 1 to k. If j - f is non-negative, it means the previous i - 1 dice could have produced sum j - f, and adding face f reaches sum j. We accumulate those counts.

We take the modulo at every addition to prevent integer overflow. Since we only add positive values and immediately reduce, the result stays within bounds.

The final answer sits at dp[n][target], the total number of ways to use all n dice to reach the exact target sum.

Visual walkthrough

Let's trace through n = 2, k = 6, target = 7. We are rolling two standard six-sided dice and counting the number of ways to get a sum of 7.

The key thing to notice is the fan-in pattern. Each cell dp[i][j] sums up to k cells from the row above. When j is large enough, all k face values contribute. When j is small, only some of them do (because j - f must be non-negative). This is why the values in row 2 grow as j increases: more face values become valid contributors.

The answer dp[2][7] = 6 matches what you know from rolling two dice: (1,6), (2,5), (3,4), (4,3), (5,2), and (6,1).

Complexity analysis

Time is O(n * target * k). For each of the n dice, you iterate over all target possible sums. For each sum, you loop over k face values. Every operation inside the innermost loop is O(1), so the total is the product of the three loop bounds.

Space for the 2D approach is O(n * target) for the full table. With the rolling-array optimization, you only keep two rows of size target + 1, reducing space to O(target). The time complexity stays the same either way.

The building blocks

1. Counting DP with bounded choices

The core pattern here is filling a DP table where each cell sums contributions from a bounded range of cells in the previous row:

for f in range(1, k + 1):
    if j - f >= 0:
        dp[i][j] = (dp[i][j] + dp[i - 1][j - f]) % MOD

This "sum over a range of predecessors" structure appears in Coin Change II (counting combinations), Combination Sum IV (counting permutations), and any problem where you pick one item from a bounded set at each step. The only differences are the loop bounds and what the "items" represent. Once you can write this inner loop from memory, you can adapt it to any counting DP variant.

2. Space optimization with a rolling array

Since row i only reads from row i - 1, you do not need the entire table:

prev = [0] * (target + 1)
prev[0] = 1
for i in range(1, n + 1):
    curr = [0] * (target + 1)
    for j in range(1, target + 1):
        for f in range(1, k + 1):
            if j - f >= 0:
                curr[j] = (curr[j] + prev[j - f]) % MOD
    prev = curr
return prev[target]

This two-array trick halves (or more) your memory usage. You will see it in every table-filling DP problem that only reads from the immediately previous row or column. The pattern is always the same: create curr, fill it from prev, then set prev = curr at the end of each outer loop iteration.

Edge cases

Before submitting, think through these scenarios:

• target is less than n: impossible. Each die contributes at least 1, so the minimum sum is n. The DP naturally returns 0 because no valid path reaches a sum below n.
• target is greater than n * k: also impossible. Each die contributes at most k, so the maximum sum is n * k. Again, the DP returns 0.
• n = 1: the answer is 1 if target is between 1 and k inclusive, and 0 otherwise. One die can hit any single face value exactly once.
• k = 1: every die shows 1, so the only reachable sum is n. The answer is 1 if target == n, and 0 otherwise.
• Large inputs: n and target can go up to 1000, and k up to 30. The 2D table would be 1000 x 1001 entries, which is about 1 million. That fits in memory. The time is 1000 * 1000 * 30 = 30 million operations, which runs well within limits.
• Modular arithmetic: always take mod at every addition. If you accumulate first and mod at the end, intermediate values can overflow in languages with fixed-width integers.

From understanding to recall

You have seen the recurrence, the table-filling order, and the space optimization. The logic is clean: each die adds a fan-in of k values from the previous row. But reproducing it from scratch under pressure is the real challenge.

The details that trip people up are small but costly. Do you initialize dp[0][0] or dp[1][0]? Does the face loop start at 0 or 1? Do you check j - f >= 0 or j - f > 0? These are not conceptual misunderstandings. They are recall failures, and they surface when you are nervous and coding fast.

Spaced repetition closes that gap. You practice writing the base case, the triple loop, and the modular accumulation from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "count the ways with bounded choices" in a problem statement, and the DP template flows out without hesitation.

Related posts

• Coin Change - The classic unbounded knapsack DP, where you minimize coins instead of counting ways, but the table-filling structure is nearly identical
• Combination Sum IV - Counting ordered sequences that sum to a target, another variation of the same "sum over predecessors" recurrence
• Target Sum - Counting ways to assign signs to reach a target, which reduces to a subset sum DP with the same counting flavor

CodeBricks breaks Number of Dice Rolls With Target Sum into its counting DP and rolling-array building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a counting DP problem shows up in your interview, you do not think about it. You just write it.