We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Dice Rolls With Target Sum

Difficulty: Medium

Problem Description

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 k^n 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 10^9 + 7.

Key Insights

  • The problem can be approached using dynamic programming due to overlapping subproblems.
  • We can define a DP table where dp[i][j] represents the number of ways to achieve a sum of j using i dice.
  • The transition involves considering each face of the dice (from 1 to k) and adding the number of ways to achieve the sum minus the current face value.
  • Edge cases include handling sums that are impossible to achieve (e.g., target values less than n or greater than n*k).

Space and Time Complexity

Time Complexity: O(n * target * k)
Space Complexity: O(n * target)

Solution

The solution employs a dynamic programming approach where we maintain a 2D array (or table) to keep track of the number of ways to achieve each possible sum with the given number of dice. The algorithm iteratively builds up the number of ways to achieve each sum for each die rolled, considering all possible outcomes from each die.

Code Solutions

def numRollsToTarget(n: int, k: int, target: int) -> int:
    MOD = 10**9 + 7
    # Create a DP table with (n+1) x (target+1)
    dp = [[0] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # Base case: one way to achieve the sum of 0 with 0 dice

    for dice in range(1, n + 1):
        for sum_value in range(1, target + 1):
            for face in range(1, k + 1):
                if sum_value - face >= 0:
                    dp[dice][sum_value] = (dp[dice][sum_value] + dp[dice - 1][sum_value - face]) % MOD

    return dp[n][target]
← Back to All Questions