Number of Dice Rolls With Target Sum - Solution & Explanation

Problem Overview: You roll n dice, each with k faces numbered from 1 to k. Count how many possible combinations produce an exact sum equal to target. The result must be returned modulo 1e9 + 7. The challenge is efficiently counting combinations without enumerating every possible roll.

Approach 1: Recursive with Memoization (Time: O(n * k * target), Space: O(n * target))

This approach models the problem as a recursive decision tree. For each die, you try every face value from 1 to k and reduce the remaining target accordingly. The state can be defined as (dice_remaining, remaining_sum). Without caching, many states repeat, causing exponential time. Memoization stores results for each state in a lookup table so repeated calls return instantly. This converts the recursion into a top‑down dynamic programming solution. The recursion depth equals the number of dice, and memoization ensures each state is computed only once.

Approach 2: Bottom-Up Dynamic Programming (Time: O(n * k * target), Space: O(n * target))

The bottom-up DP version builds the solution iteratively. Define dp[i][s] as the number of ways to get sum s using i dice. Start with the base case dp[0][0] = 1. For each dice count from 1 to n, iterate through all possible sums and accumulate contributions from the previous row: dp[i][s] += dp[i-1][s-face] for every face value 1..k. This approach avoids recursion and is often easier to reason about in interviews. The transition mirrors the recurrence used in the recursive solution but computed iteratively using a DP table.

Recommended for interviews: Start by describing the recursive state definition and recurrence to demonstrate understanding of the combinatorial structure. Then move to memoization or bottom-up dynamic programming to eliminate repeated work. Interviewers typically expect the DP formulation with complexity O(n * k * target), since brute force enumeration would be exponential and impractical.