mediumDynamic Programming 2DPure DSA~25 min
Ways to Roll Dice Summing to a Target
You roll n identical dice, each showing 1..k. Count the distinct ordered outcomes whose face values add up to a target total.
Problem
Given integers n (number of dice), k (faces per die, values 1..k), and target, return the number of ordered ways the dice can sum to exactly target, modulo 1e9 + 7.
Input
Three integers n, k, and target.
Output
An integer: the number of ways modulo 1e9 + 7.
Constraints
- 1 <= n, k <= 1000
- 1 <= target <= 1000
Examples
Example 1
Input
n = 2, k = 6, target = 7
Output
6
(1,6),(2,5),(3,4),(4,3),(5,2),(6,1).
Example 2
Input
n = 1, k = 6, target = 3
Output
1
Only the single roll of 3.