1155. Number of Dice Rolls with Target Sum - Explanation

1. Recursion

Intuition

This is a counting problem where we need to find all ways to roll n dice (each with k faces) to get a sum of target. For each die, we can roll any value from 1 to k, and we need to count how many combinations lead to the target. This naturally leads to a recursive approach: for each die roll, we try all possible face values and recursively count the ways to achieve the remaining target with the remaining dice.

Algorithm

Define a recursive function count(n, target) that returns the number of ways to reach target using n dice.
Base case: If n == 0, return 1 if target == 0 (found a valid combination), else return 0.
If target < 0, return 0 (invalid path).
For each face value from 1 to k, recursively count ways with n - 1 dice and target - val.
Sum up all the ways and return the result modulo 10^9 + 7.

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7

        def count(n, target):
            if n == 0:
                return 1 if target == 0 else 0
            if target < 0:
                return 0

            res = 0
            for val in range(1, k + 1):
                res = (res + count(n - 1, target - val)) % MOD
            return res

        return count(n, target)

Time & Space Complexity

Time complexity: $O(k ^ n)$
Space complexity: $O(n)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems. For example, reaching target 10 with 3 dice might be computed multiple times through different paths. By caching results in a memoization table, we avoid redundant calculations. The state is defined by two variables: the number of dice remaining and the current target sum.

Algorithm

Create a cache (dictionary or 2D array) to store computed results.
Define a recursive function count(n, target) with memoization.
Base case: If n == 0, return 1 if target == 0, else return 0.
If target < 0, return 0.
If the result for (n, target) is already cached, return it.
For each face value from 1 to k (where target - val >= 0), add the recursive result.
Store the result in the cache and return it.

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        cache = {}

        def count(n, target):
            if n == 0:
                return 1 if target == 0 else 0
            if (n, target) in cache:
                return cache[(n, target)]

            res = 0
            for val in range(1, k + 1):
                if target - val >= 0:
                    res = (res + count(n - 1, target - val)) % MOD
            cache[(n, target)] = res
            return res

        return count(n, target)

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(n * t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion with memoization, we can build the solution iteratively from the ground up. We use a 2D DP table where dp[i][t] represents the number of ways to achieve sum t using exactly i dice. We fill this table by considering each die one at a time and each possible face value.

Algorithm

Create a 2D array dp of size (n + 1) x (target + 1), initialized to 0.
Set dp[0][0] = 1 (one way to achieve sum 0 with 0 dice).
For each die i from 1 to n:
- For each face value val from 1 to k:
  - For each possible sum t from val to target:
    - Add dp[i - 1][t - val] to dp[i][t].
Return dp[n][target].

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 val in range(1, k + 1):
                for t in range(val, target + 1):
                    dp[i][t] = (dp[i][t] + dp[i - 1][t - val]) % MOD

        return dp[n][target]

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(n * t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

4. Dynamic Programming (Space Optimized)

Intuition

In the bottom-up approach, we only need the previous row to compute the current row. This observation allows us to reduce space from O(n * target) to O(target) by using two 1D arrays: one for the current state and one for the next state. After processing each die, we swap the arrays.

Algorithm

Create a 1D array dp of size target + 1, initialized to 0.
Set dp[0] = 1.
For each die (from 0 to n - 1):
- Create a new array next_dp initialized to 0.
- For each face value val from 1 to k:
  - For each sum total from val to target:
    - Add dp[total - val] to next_dp[total].
- Replace dp with next_dp.
Return dp[target].

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        MOD = 10**9 + 7

        for dice in range(n):
            next_dp = [0] * (target + 1)
            for val in range(1, k + 1):
                for total in range(val, target + 1):
                    next_dp[total] = (next_dp[total] + dp[total - val]) % MOD
            dp = next_dp

        return dp[target]

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

5. Dynamic Programming (Optimal)

Intuition

We can use a single array and iterate backwards to avoid overwriting values we still need. By processing sums in reverse order and resetting values before adding new contributions, we achieve the same result with a single array. This approach also skips positions with zero ways, providing a minor optimization.

Algorithm

Create a 1D array dp of size target + 1, initialized to 0.
Set dp[0] = 1.
For each die (from 0 to n - 1):
- Iterate t from target down to 0:
  - Store the current value ways = dp[t] and reset dp[t] = 0.
  - If ways > 0, for each face value val from 1 to min(k, target - t):
    - Add ways to dp[t + val].
Return dp[target].

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (target + 1)
        dp[0] = 1

        for dice in range(n):
            for t in range(target, -1, -1):
                ways = dp[t]
                dp[t] = 0
                if ways:
                    for val in range(1, min(k + 1, target - t + 1)):
                        dp[t + val] = (dp[t + val] + ways) % MOD

        return dp[target]

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

Common Pitfalls

Forgetting Modulo Operations

Not applying the modulo operation (% (10^9 + 7)) after each addition causes integer overflow. The number of ways can grow extremely large, exceeding the maximum value of 32-bit or even 64-bit integers. Apply modulo after every addition to keep values within bounds and avoid overflow errors.

Incorrect Base Case Handling

Setting the wrong base case in the DP leads to incorrect counts. When n == 0 (no dice left), the only valid result is if target == 0 (we exactly hit the target), returning 1. If target != 0 with no dice remaining, return 0. Mixing up these conditions produces wrong answers for edge cases.

Off-by-One Errors in Face Values

Starting the face value loop at 0 instead of 1, or going up to k - 1 instead of k, miscounts the valid dice rolls. Each die has faces numbered 1 through k (not 0 through k-1). Ensure your loop iterates from 1 to k inclusive to correctly enumerate all possible face values.