bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium2-D Dynamic ProgrammingLC 1155

Number of Dice Rolls With Target Sum

You have n dice, and each die 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.

Asked at 4 companies
AmazonBloombergGoogle
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode