Number of Dice Rolls With Target Sum
Problem
You have n dice, each with k faces numbered 1 to k. Return the number of ordered ways to roll them so the sum equals target, modulo 10⁹ + 7.
n = 2, k = 6, target = 76def num_rolls_to_target(n, k, target):
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 s in range(1, target + 1):
for f in range(1, k + 1):
if s - f >= 0:
dp[i][s] = (dp[i][s] + dp[i-1][s-f]) % MOD
return dp[n][target]function numRollsToTarget(n, k, target) {
const MOD = 1000000007n;
const dp = Array.from({length: n + 1}, () => Array(target + 1).fill(0n));
dp[0][0] = 1n;
for (let i = 1; i <= n; i++) {
for (let s = 1; s <= target; s++) {
for (let f = 1; f <= k; f++) {
if (s - f >= 0) dp[i][s] = (dp[i][s] + dp[i-1][s-f]) % MOD;
}
}
}
return Number(dp[n][target]);
}class Solution {
public int numRollsToTarget(int n, int k, int target) {
final int MOD = 1_000_000_007;
long[][] dp = new long[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int s = 1; s <= target; s++) {
for (int f = 1; f <= k; f++) {
if (s - f >= 0) dp[i][s] = (dp[i][s] + dp[i-1][s-f]) % MOD;
}
}
}
return (int) dp[n][target];
}
}int numRollsToTarget(int n, int k, int target) {
const int MOD = 1e9 + 7;
vector<vector<long long>> dp(n + 1, vector<long long>(target + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int s = 1; s <= target; s++) {
for (int f = 1; f <= k; f++) {
if (s - f >= 0) dp[i][s] = (dp[i][s] + dp[i-1][s-f]) % MOD;
}
}
}
return (int) dp[n][target];
}Explanation
We want to count the ordered ways to roll n dice (each with faces 1..k) so their sum hits target. The idea is to build the answer up one die at a time with a 2D table where dp[i][s] = the number of ways the first i dice can total exactly s.
The base case is dp[0][0] = 1: there is exactly one way to make a sum of 0 using zero dice (roll nothing). Every other dp[0][s] is 0.
To fill dp[i][s], we think about what the i-th die showed. If it showed face f, the first i-1 dice must have made s - f. So we sum dp[i-1][s-f] over every face f from 1 to k (whenever s - f >= 0), taking everything modulo 10^9 + 7 to keep numbers small.
Example: n = 2, k = 6, target = 7. The pairs that work are (1,6),(2,5),(3,4),(4,3),(5,2),(6,1) — exactly 6 ordered ways, which is what dp[2][7] computes.
The answer lives in dp[n][target]. The triple loop over dice, sums, and faces gives the O(n · target · k) running time.