1155. Number of Dice Rolls With Target Sum

Problem Description

Given n dice, each with k faces numbered from 1 to k, and a target sum target, find the number of possible ways to roll the dice such that the sum of the face-up numbers equals target. The result should be modulo 10<sup>9</sup> + 7.

Solution: Dynamic Programming

This problem can be efficiently solved using dynamic programming. We'll create a 2D array (or a 1D array optimized for space) to store the number of ways to achieve a given sum with a given number of dice.

Approach:

1. Initialization: Create a DP array dp.

   • For a 2D approach (dp[i][j] represents ways to get sum j using i dice), initialize dp[0][0] = 1.
   • For a 1D optimized approach (dp[j] represents ways to get sum j), initialize dp[0] = 1.

2. Iteration: Iterate through the number of dice (i) from 1 to n. For each die:

   • Iterate through possible sums (j) from 1 to target.
   • For each sum j, iterate through possible outcomes (h) of the current die (from 1 to k or min(j, k)).
   • Update dp[i][j] (or dp[j] in the optimized version) by adding the number of ways to achieve the remaining sum (j - h) using the previous dice (i - 1). This is done modulo 10<sup>9</sup> + 7 to avoid integer overflow.

3. Result: The final answer will be dp[n][target] (or dp[target] in the optimized version).

Time and Space Complexity:

• 2D DP: Time complexity: O(n * k * target), Space complexity: O(n * target)
• 1D DP (Optimized): Time complexity: O(n * k * target), Space complexity: O(target)

The optimized 1D approach significantly reduces space complexity because we only need to store results for the current sum at any given point.

Code Implementation (Multiple Languages)

Python (2D DP):

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        mod = 10**9 + 7
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, target + 1):
                for h in range(1, min(j, k) + 1):
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - h]) % mod
        return dp[n][target]

Python (1D DP Optimized):

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        mod = 10**9 + 7
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            new_dp = [0] * (target + 1)
            for j in range(1, target + 1):
                for h in range(1, min(j, k) + 1):
                    new_dp[j] = (new_dp[j] + dp[j - h]) % mod
            dp = new_dp
        return dp[target]

Java (2D DP): Similar structure to the Python 2D DP solution.

Java (1D DP Optimized): Similar structure to the Python 1D DP optimized solution.

C++, Go, TypeScript, and Rust: The implementation in these languages will follow a similar pattern to the Python examples, adapting the syntax and data structures accordingly. (Refer to the original response for complete code examples in these languages).

Detailed Explanation of the Optimized 1D DP Approach (Python)

The optimized 1D approach reduces space complexity. Let's trace how it works:

• We start with dp = [0] * (target + 1), dp[0] = 1.
• The outer loop iterates through the dice (i). The inner loops calculate the number of ways to achieve each sum (j) using i dice.
• new_dp temporarily stores the results for the current iteration.
• After the inner loops finish for a given i, dp is updated to new_dp, overwriting the previous results—this is the key to saving space.

This dynamic programming approach efficiently calculates the number of ways to obtain the target sum by building upon solutions for smaller subproblems (fewer dice and smaller sums). The modulo operation prevents integer overflow, ensuring that the results remain within a manageable range.