< Back





1155. Number of Dice Rolls With Target Sum

Similar to the coin change problem, but instead of coins having a fixed value the coins can have a
value up to k, with k being the number of faces on a die. We're asked to determine how many unique
combinations of n die with k faces make the target value, target.

Using dynamic programming, we can avoid recomputing already solved solutions. I would provide you
with the bottom-up approach using a table but, frankly, this problem makes more sense if we use
recursion with memoization - a top-down approach. The two approaches have the same complexity, so
we're going to stick with the easier one to understand.

We'll start with the base case for our recursion. Once we've rolled all n die, if the sum of our
dice doesn't equal the target, we return 0, else we return 1 - we've found a combination.

For the recursion, while we're picking die, we'll roll one but we're only accepting values from 1 to
k (inclusive) or the amount remaining for us to reach the target (inclusive). Why? Well if we've
already rolled some die and the current amount remaining to reach the target is less than the number
of faces, there's no point in rolling for all the faces. Once we've picked a face for the die, we
increase the number of die we've rolled and add the face value to our sum. Then we'll recursively
move to the next die.

Once this recursion collapses, we'll have recorded all the combinations of n die with k faces that
give us the target value. Memoization prevents duplicate work.

The solution is as follows:


  class Solution:
      def numRollsToTarget(self, n: int, k: int, target: int) -> int:
          mod = int(10e8 + 7)

          @cache
          def dp(i: int, t: int) -> int:
              if i == n:
                  return 1 if t == target else 0

              ans = 0

              for j in range(1, min(k + 1, target - t + 1)):
                  ans += dp(i + 1, t + j)

              return ans

          return dp(0, 0) % mod


_ Time Complexity:

  O(n * t * k) - Where n is the number of die, t is the target, and k is the number of faces, this
  is the number of different paths we can traverse while executing this recursive algorithm.

_ Space Complexity:

  O(n * t) - The recursive call stack can reach size n * t.