Number of Dice Rolls With Target Sum

Number of Dice Rolls With Target Sum

What is this problem about?

The Number of Dice Rolls With Target Sum problem asks: given n dice each with k faces (labeled 1 to k), how many ways can you roll all n dice to get a total sum equal to target? Return the answer modulo 10^9+7. This is a classic unbounded knapsack / partition DP problem on dice.

Why is this asked in interviews?

Citadel, Meta, Amazon, Google, and Bloomberg ask this because it cleanly demonstrates the DP "roll by roll" state transition. It validates understanding of partition counting with fixed item sizes and modular arithmetic. The dynamic programming interview pattern is directly and cleanly demonstrated.

Algorithmic pattern used

DP with rolling array. dp[i][j] = number of ways to get sum j using exactly i dice. Transition: for each die face f (1 to k), dp[i][j] += dp[i-1][j-f]. Base case: dp[0][0] = 1. Answer: dp[n][target]. Optimize space to O(target) using a 1D DP array updated in reverse or with a copy.

Example explanation

n=2, k=6, target=7. Ways: (1,6),(2,5),(3,4),(4,3),(5,2),(6,1) = 6 ways. DP: dp[0][0]=1. After die 1: dp[1][1..6]=1 each. After die 2: dp[2][7] = dp[1][1]+dp[1][2]+...+dp[1][6] = 6 ✓.

Common mistakes candidates make

• Not applying modulo at each step (overflow for large n, k, target).
• Iterating dp[i][j] in wrong order (using updated values from current die instead of previous).
• Off-by-one: die faces are 1 to k, not 0 to k.
• Using dp[i-1][j-f] with negative j-f indices (need bounds check).

Interview preparation tip

Dice/coin counting DP problems follow the same template: dp[items][sum], transition adds each face/denomination value, answer is dp[n][target]. The key difference from unbounded knapsack: here each die is used exactly once (bounded). Practice this problem, coin change (unbounded), and 0/1 knapsack as the three fundamental DP partition patterns. Modular arithmetic must be applied at each addition step — not just at the end.