diff options
Diffstat (limited to 'num_dice_roll_target_sum.c')
-rw-r--r-- | num_dice_roll_target_sum.c | 40 |
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 +} |