Number of Dice Rolls With Target Sum

How it works

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.

Steps

1. Create a 1D array dp of size target + 1, initialized to 0.
2. Set dp[0] = 1.
3. 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].
4. Return dp[target].

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.

Things to watch for

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.

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]

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        const int MOD = 1e9 + 7;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int dice = 0; dice < n; dice++) {
            for (int t = target; t >= 0; t--) {
                int ways = dp[t];
                dp[t] = 0;
                if (ways > 0) {
                    for (int val = 1; val <= min(k, target - t); val++) {
                        dp[t + val] = (dp[t + val] + ways) % MOD;
                    }
                }
            }
        }

        return dp[target];
    }
};