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.
1#include <stdio.h>
2#include <string.h>
3#define MOD 1000000007
4
5int memo[31][1001];
6
7int dfs(int dice, int target, int k) {
8 if (dice == 0) return target == 0;
9 if (target <= 0) return 0;
10 if (memo[dice][target] != -1) return memo[dice][target];
11 int count = 0;
12 for (int i = 1; i <= k; ++i) {
13 count = (count + dfs(dice - 1, target - i, k)) % MOD;
14 }
15 return memo[dice][target] = count;
16}
17
18int numRollsToTarget(int n, int k, int target) {
19 memset(memo, -1, sizeof(memo));
20 return dfs(n, target, k);
21}
22
23int main() {
24 printf("%d\n", numRollsToTarget(2, 6, 7)); // Output: 6
25 return 0;
26}The function dfs recursively tries each face of the dice and reduces the number of dice and the target sum accordingly. The result is stored in the memoization table memo to avoid recomputation. The base case handles no dice left or negative target state.
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.
1
The solution applies DP logic to process results by iterating constraints of dice and result values using accumulated states from previously computed possibilities.