Watch 10 video solutions for Number of Dice Rolls With Target Sum, a medium level problem involving Dynamic Programming. This walkthrough by NeetCodeIO has 23,349 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have n dice, and each dice has k faces numbered from 1 to k.
Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: n = 1, k = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.
Example 2:
Input: n = 2, k = 6, target = 7 Output: 6 Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
Example 3:
Input: n = 30, k = 30, target = 500 Output: 222616187 Explanation: The answer must be returned modulo 109 + 7.
Constraints:
1 <= n, k <= 301 <= target <= 1000Problem Overview: You roll n dice, each with k faces numbered from 1 to k. Count how many possible combinations produce an exact sum equal to target. The result must be returned modulo 1e9 + 7. The challenge is efficiently counting combinations without enumerating every possible roll.
Approach 1: Recursive with Memoization (Time: O(n * k * target), Space: O(n * target))
This approach models the problem as a recursive decision tree. For each die, you try every face value from 1 to k and reduce the remaining target accordingly. The state can be defined as (dice_remaining, remaining_sum). Without caching, many states repeat, causing exponential time. Memoization stores results for each state in a lookup table so repeated calls return instantly. This converts the recursion into a top‑down dynamic programming solution. The recursion depth equals the number of dice, and memoization ensures each state is computed only once.
Approach 2: Bottom-Up Dynamic Programming (Time: O(n * k * target), Space: O(n * target))
The bottom-up DP version builds the solution iteratively. Define dp[i][s] as the number of ways to get sum s using i dice. Start with the base case dp[0][0] = 1. For each dice count from 1 to n, iterate through all possible sums and accumulate contributions from the previous row: dp[i][s] += dp[i-1][s-face] for every face value 1..k. This approach avoids recursion and is often easier to reason about in interviews. The transition mirrors the recurrence used in the recursive solution but computed iteratively using a DP table.
Recommended for interviews: Start by describing the recursive state definition and recurrence to demonstrate understanding of the combinatorial structure. Then move to memoization or bottom-up dynamic programming to eliminate repeated work. Interviewers typically expect the DP formulation with complexity O(n * k * target), since brute force enumeration would be exponential and impractical.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * k * target) | O(n * target) | When you want a natural recursive formulation and easy state definition |
| Bottom-Up Dynamic Programming | O(n * k * target) | O(n * target) | Preferred iterative solution for interviews and production code |
| Space-Optimized DP | O(n * k * target) | O(target) | When memory usage matters and only the previous dice state is needed |