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 <= 1000The #1155 Number of Dice Rolls With Target Sum problem asks you to determine how many ways you can roll d dice (each having f faces) so that the total sum equals a given target. This is a classic Dynamic Programming counting problem where we build solutions for smaller subproblems and reuse them.
A common strategy is to define a DP state such as dp[i][s], representing the number of ways to achieve sum s using i dice. For each die, you iterate through all possible face values and update the possible sums. This builds the result layer by layer from 1 die up to d dice.
Because the number of combinations can grow large, the result is typically taken modulo 1e9+7. The straightforward DP approach considers all dice and face values, leading to a time complexity of O(d * f * target) and space complexity of O(d * target). With space optimization, the DP table can be reduced to O(target).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D DP) | O(d * f * target) | O(d * target) |
| Space Optimized DP | O(d * f * target) | O(target) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming. The states are how many dice are remaining, and what sum total you have rolled so far.
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.
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.
1using System;
2
3public class Solution {
4 private static readonly int MOD = 1000000007;
5 public int NumRollsToTarget(int n, int k, int target) {
6 var memo = new int[n + 1, target + 1];
7 for (int i = 0; i <= n; i++)
8 for (int j = 0; j <= target; j++)
9 memo[i, j] = -1;
10 return Dfs(n, target, k, memo);
11 }
12
13 private int Dfs(int dice, int target, int k, int[,] memo) {
14 if (dice == 0) return target == 0 ? 1 : 0;
if (target <= 0) return 0;
if (memo[dice, target] != -1) return memo[dice, target];
int count = 0;
for (int i = 1; i <= k; ++i) {
count = (count + Dfs(dice - 1, target - i, k, memo)) % MOD;
}
return memo[dice, target] = count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumRollsToTarget(2, 6, 7)); // Output: 6
}
}The C# solution uses memoization alongside recursion. The recursive Dfs method evaluates each dice roll path, storing results for each state configuration in the memo array.
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.
Time Complexity: O(n * target * k) due to nested loops.
Space Complexity: O(n * target) for the DP table.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, instead of maintaining a full 2D DP table, you can use a rolling 1D array. Since each step only depends on results from the previous number of dice, this reduces the space complexity from O(d * target) to O(target).
Yes, this problem is a common dynamic programming interview question. It tests understanding of state transitions, combinational counting, and optimization techniques often expected in technical interviews.
A dynamic programming table or array is the most suitable data structure. It stores intermediate results for combinations of dice and sums, allowing the algorithm to reuse previously computed values and improve performance.
The optimal approach uses dynamic programming. By defining a state that tracks the number of ways to reach a certain sum with a given number of dice, you can iteratively build the solution. This avoids recomputation and efficiently counts all valid combinations.
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.