Sponsored
Sponsored
We utilize recursion to explore different combinations of dice rolls to reach the target sum. For every die, we try all face values and keep track of the sum formed. To avoid redundant calculations, we use memoization.
Time Complexity: O(n * target * k) because there are n * target states and we iterate up to k times in the worst case.
Space Complexity: O(n * target) for the memoization table.
1MOD = 10**9 + 7
2
3def numRollsToTarget(n, k, target):
4 memo = [[-1] * (target + 1) for _ in range(n + 1)]
5
6 def dfs(dice, target):
7 if dice == 0:
8 return 1 if target == 0 else 0
9 if target < 0:
10 return 0
11 if memo[dice][target] != -1:
12 return memo[dice][target]
13 count = 0
14 for i in range(1, k + 1):
15 count = (count + dfs(dice - 1, target - i)) % MOD
16 memo[dice][target] = count
17 return count
18
19 return dfs(n, target)
20
21print(numRollsToTarget(2, 6, 7)) # Output: 6We define a recursive function dfs to attempt different face values for each die, decrementing dice and target step-wise. The results for already computed states are kept in a list named memo to prevent recomputation.
Use a Dynamic Programming (DP) table where dp[i][j] represents the number of ways to achieve sum j with i dice. Initially, only dp[0][0] = 1 since there's one way to roll zero dice to get zero sum. The state transition iterates over each dice and accumulates ways using previous results.
Time Complexity: O(n * target * k) due to nested loops.
Space Complexity: O(n * target) for the DP table.
The DP table dp is built iteratively. For each dice i, calculate possible sums j using results from the previous dice count i-1 and adjusting the target by each face value x.