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 <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int numRollsToTarget(int n, int k, int target) {
7 std::vector<std::vector<int>> memo(n + 1, std::vector<int>(target + 1, -1));
8 const int MOD = 1e9 + 7;
9 return dfs(n, target, k, memo, MOD);
10 }
11
12private:
13 int dfs(int dice, int target, int k, std::vector<std::vector<int>>& memo, const int MOD) {
14 if (dice == 0) return target == 0 ? 1 : 0;
15 if (target <= 0) return 0;
16 if (memo[dice][target] != -1) return memo[dice][target];
17 int count = 0;
18 for (int i = 1; i <= k; ++i) {
19 count = (count + dfs(dice - 1, target - i, k, memo, MOD)) % MOD;
20 }
21 return memo[dice][target] = count;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::cout << sol.numRollsToTarget(2, 6, 7) << std::endl; // Output: 6
28 return 0;
29}This solution uses recursion enhanced by a memoization table to track the solutions of the subproblems formed by reducing dice and target. The base case checks for no dice left or negative targets, returning 1 if the target is zero and 0 otherwise.
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.
public class Solution {
public int NumRollsToTarget(int n, int k, int target) {
const int MOD = 1000000007;
int[,] dp = new int[n + 1, target + 1];
dp[0, 0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
for (int x = 1; x <= k; x++) {
if (j >= x) {
dp[i, j] = (dp[i, j] + dp[i - 1, j - x]) % MOD;
}
}
}
}
return dp[n, target];
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumRollsToTarget(2, 6, 7)); // Output: 6
}
}DP table builds progressively from baseline dice configurations summed over potential achievable numbers. The combined effect allows cumulative state transitioning for result evaluation.