Problem statement

You have n dice, each with k faces numbered 1 through k.

Return the number of ways to roll all the dice so the face values sum to exactly target. Since the answer may be large, return it modulo 10^9 + 7.

Example 1

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

Example 2

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

Example 3

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

Constraints

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

Hints for Number of Dice Rolls With Target Sum

1. Hint 1

   Add one die at a time: dp[die][t] = Σ dp[die-1][t - face] over the k faces.

2. Hint 2

   Only the previous die's row is needed, so two rolling arrays suffice.

3. Hint 3

   Take the modulus as you accumulate, not only at the end.

How to solve Number of Dice Rolls With Target Sum

Add one die at a time: dp[t] after d dice is Σ dp_prev[t - face] over the faces 1..k.

Approach

1. Start dp[0] = 1.
2. Repeat n times: nxt[t] = Σ dp[t - f] for f in 1..min(k, t), modulo 10⁹+7.
3. Return dp[target].

Why it works

The last die shows some face f, and the remaining dice must sum to t - f; summing over faces counts every roll exactly once.

Complexity

• Time — O(n · target · k)
• Space — O(target)

Pitfalls

• Reduce modulo as you go; the raw counts overflow quickly.
• A prefix-sum over the previous row drops the inner factor of k.

Reference solution

Python

def numRollsToTarget(n: int, k: int, target: int) -> int:
    MOD = 1000000007
    dp = [0] * (target + 1)
    dp[0] = 1
    for _ in range(n):
        nxt = [0] * (target + 1)
        for t in range(1, target + 1):
            total = 0
            for face in range(1, min(k, t) + 1):
                total += dp[t - face]
            nxt[t] = total % MOD
        dp = nxt
    return dp[target]

Java

public static int numRollsToTarget(int n, int k, int target) {
    final int MOD = 1000000007;
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int die = 1; die <= n; die++) {
        int[] next = new int[target + 1];
        for (int t = 1; t <= target; t++) {
            int sum = 0;
            for (int face = 1; face <= k && face <= t; face++) {
                sum = (sum + dp[t - face]) % MOD;
            }
            next[t] = sum;
        }
        dp = next;
    }
    return dp[target];
}

C++

int numRollsToTarget(int n, int k, int target) {
    const int MOD = 1000000007;
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int die = 1; die <= n; die++) {
        vector<int> next(target + 1, 0);
        for (int t = 1; t <= target; t++) {
            int sum = 0;
            for (int face = 1; face <= k && face <= t; face++) {
                sum = (sum + dp[t - face]) % MOD;
            }
            next[t] = sum;
        }
        dp = next;
    }
    return dp[target];
}

JavaScript

var numRollsToTarget = function(n, k, target) {
    const MOD = 1000000007;
    let dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (let die = 1; die <= n; die++) {
        const next = new Array(target + 1).fill(0);
        for (let t = 1; t <= target; t++) {
            let sum = 0;
            for (let face = 1; face <= k && face <= t; face++) {
                sum = (sum + dp[t - face]) % MOD;
            }
            next[t] = sum;
        }
        dp = next;
    }
    return dp[target];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Largest BST in a Binary Tree Medium
• Longest ZigZag Path in a Binary Tree Medium
• House Robber III Medium
• Find Good Days to Rob the Bank Medium
• Minimum Increments to Equalize Leaf Paths Medium
• Disconnect Path in a Binary Matrix by at Most One Flip Medium