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 <= 1000We 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * target * k) due to nested loops.
Space Complexity: O(n * target) for the DP table.
| 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. |
Number of Dice Rolls with Target Sum - Leetcode 1155 - Python • NeetCodeIO • 20,418 views views
Watch 9 more video solutions →Practice Number of Dice Rolls With Target Sum with our built-in code editor and test cases.
Practice on FleetCode