Number of Dice Rolls With Target Sum - Solution & Explanation
Problem Statement
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 <= 1000
Approach Overview
Problem 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 1: Approach 1: Recursive with Memoization
We utilize recursion to explore different combinations of dice rolls to reach the target sum. For every die, we try all face values and keep track of the sum formed. To avoid redundant calculations, we use memoization.
The function dfs recursively tries each face of the dice and reduces the number of dice and the target sum accordingly. The result is stored in the memoization table memo to avoid recomputation. The base case handles no dice left or negative target state.
Complexity
Time Complexity: O(n * target * k) because there are n * target states and we iterate up to k times in the worst case.
Space Complexity: O(n * target) for the memoization table.
Approach 2: Approach 2: Dynamic Programming
Use a Dynamic Programming (DP) table where dp[i][j] represents the number of ways to achieve sum j with i dice. Initially, only dp[0][0] = 1 since there's one way to roll zero dice to get zero sum. The state transition iterates over each dice and accumulates ways using previous results.
The DP table dp is built iteratively. For each dice i, calculate possible sums j using results from the previous dice count i-1 and adjusting the target by each face value x.
Complexity
Time Complexity: O(n * target * k) due to nested loops.
Space Complexity: O(n * target) for the DP table.
Approach 3: Dynamic Programming
We define f[i][j] as the number of ways to get a sum of j using i dice. Then, we can obtain the following state transition equation:
$
f[i][j] = sum_{h=1}^{min(j, k)} f[i-1][j-h]
where h represents the number of points on the i-th die.
Initially, we have f[0][0] = 1, and the final answer is f[n][target].
The time complexity is O(n times k times target), and the space complexity is O(n times target).
We notice that the state f[i][j] only depends on f[i-1][], so we can use a rolling array to optimize the space complexity to O(target)$.
Approach 4: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Recursive with Memoization | Time Complexity: O(n * target * k) because there are n * target states and we iterate up to k times in the worst case. |
| Approach 2: Dynamic Programming | Time Complexity: O(n * target * k) due to nested loops. |
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Number of Dice Rolls with Target Sum - Leetcode 1155 - Python • NeetCodeIO • 23,891 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Dice Rolls With Target Sum easy or hard?
Number of Dice Rolls With Target Sum Python/Java solution
How to solve Number of Dice Rolls With Target Sum in O(n)?
What is the best approach for Number of Dice Rolls With Target Sum?
Is Number of Dice Rolls With Target Sum asked at Google/Amazon/Meta?
What data structure is used in Number of Dice Rolls With Target Sum?
What is the time complexity of Number of Dice Rolls With Target Sum?
Ready to solve this problem?
Practice Number of Dice Rolls With Target Sum with our built-in code editor and test cases.
Practice on FleetCode