aboutsummaryrefslogtreecommitdiff
path: root/num_dice_roll_target_sum.c
diff options
context:
space:
mode:
Diffstat (limited to 'num_dice_roll_target_sum.c')
-rw-r--r--num_dice_roll_target_sum.c40
1 files changed, 40 insertions, 0 deletions
diff --git a/num_dice_roll_target_sum.c b/num_dice_roll_target_sum.c
new file mode 100644
index 0000000..df19cbf
--- /dev/null
+++ b/num_dice_roll_target_sum.c
@@ -0,0 +1,40 @@
+// 1155. Number of Dice Rolls With Target Sum
+#include "leetcode.h"
+
+/*
+ * you have 'n' dice and die has 'k' faces numbered 1 to 'k'. given three
+ * integers 'n', 'k', and 'target', return the number of possible ways to roll
+ * the dice so the sum of the face up numbers equals 'target'. since the answer
+ * may be too large, return it modulo 10e9+7
+ */
+
+int numRollsToTarget(int n, int k, int target) {
+ int mod = 1e9 + 7;
+ int **dp = malloc((n + 1) * sizeof(int *));
+ for (int i = 0; i <= n; i++)
+ dp[i] = calloc(target + 1, sizeof(int));
+ for (int i = 1; i <= target; i++) {
+ if (i > k)
+ break;
+ dp[1][i] = 1;
+ }
+ for (int i = 2; i <= n; i++)
+ for (int j = i; j <= target; j++) {
+ if (j > i * k)
+ break;
+ int sum = 0;
+ for (int m = 1; m <= k; m++) {
+ if (j - m < 0)
+ break;
+ sum = (sum + dp[i - 1][j - m] % mod);
+ }
+ dp[i][j] = sum;
+ }
+ return dp[n][target];
+}
+
+int main() {
+ printf("%d\n", numRollsToTarget(1, 6, 3)); // expect: 1
+ printf("%d\n", numRollsToTarget(2, 6, 7)); // expect: 6
+ printf("%d\n", numRollsToTarget(30, 30, 500)); // expect: 222616187
+}