101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Dynamic Programming (2D) - Complex approach
  2. Dynamic Programming (1D) - Complex approach

Approach 1: Dynamic Programming (2D)

The key insight for solving this problem is to use dynamic programming to count the number of ways to achieve the target sum.

Let's define a 2D DP array dp[i][j] where:

  • i represents the number of dice used (from 1 to n)
  • j represents the current sum (from 1 to target)

The value dp[i][j] represents the number of ways to achieve a sum of j using i dice.

The base cases are:

  • dp[0][0] = 1 (there is one way to achieve a sum of 0 using 0 dice, which is by not rolling any die)

For the recurrence relation, we need to consider all possible values of the current die (from 1 to k):

dp[i][j] = sum(dp[i-1][j-face]) for all face from 1 to k, where j-face >= 0

In other words, to find the number of ways to achieve a sum of j using i dice, we consider all possible values of the current die (from 1 to k) and sum up the number of ways to achieve a sum of j-face using i-1 dice.

The final answer is dp[n][target].

Algorithm:

  1. Initialize a 2D DP array dp of size (n+1) × (target+1), where dp[i][j] represents the number of ways to achieve a sum of j using i dice.
  2. Set the base case: dp[0][0] = 1.
  3. For each number of dice i from 1 to n:
  4. a. For each possible sum j from 1 to target:
  5. i. For each possible face value face from 1 to k:
  6. 1. If j-face >= 0, then dp[i][j] += dp[i-1][j-face]
  7. ii. Apply modulo 10^9 + 7 to dp[i][j]
  8. Return dp[n][target].

Time Complexity:

O(n * target * k)

We need to compute the DP values for each number of dice, each possible sum, and each possible face value. There are n dice, target possible sums, and k possible face values.

Space Complexity:

O(n * target)

We use a 2D DP array of size (n+1) × (target+1) to store the number of ways to achieve each sum using each number of dice.

Approach 2: Dynamic Programming (1D)

We can optimize the space complexity by observing that to compute the DP values for the current number of dice, we only need the DP values for the previous number of dice.

Instead of using a 2D DP array, we can use two 1D arrays: curr and prev, each of size target+1, to store the DP values for the current number of dice and the previous number of dice, respectively.

After computing the DP values for the current number of dice, we update prev to curr and reset curr for the next number of dice.

The recurrence relation remains the same:

curr[j] = sum(prev[j-face]) for all face from 1 to k, where j-face >= 0

The final answer is prev[target] after the last iteration.

Algorithm:

  1. Initialize two 1D arrays prev and curr, each of size target+1, where prev[j] represents the number of ways to achieve a sum of j using i-1 dice.
  2. Set the base case: prev[0] = 1.
  3. For each number of dice i from 1 to n:
  4. a. Reset curr to all zeros.
  5. b. For each possible sum j from 1 to target:
  6. i. For each possible face value face from 1 to k:
  7. 1. If j-face >= 0, then curr[j] += prev[j-face]
  8. ii. Apply modulo 10^9 + 7 to curr[j]
  9. c. Update prev = curr.
  10. Return prev[target].

Time Complexity:

O(n * target * k)

The time complexity remains the same as the 2D DP approach, as we still need to compute the DP values for each number of dice, each possible sum, and each possible face value.

Space Complexity:

O(target)

We only use two 1D arrays of size target+1, which is a significant improvement over the 2D DP approach.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function numRollsToTarget(n, k, target):
    MOD = 10^9 + 7
 
    // Initialize DP array
    dp = new 2D array of size (n+1) × (target+1), initialized with 0
 
    // Base case
    dp[0][0] = 1
 
    // Fill DP array
    for i from 1 to n:
        for j from 1 to target:
            for face from 1 to k:
                if j - face >= 0:
                    dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD
 
    return dp[n][target]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone