aboutsummaryrefslogtreecommitdiff
path: root/num_dice_roll_target_sum.c
blob: df19cbf5185071f5a50f5cadd4701f3335bdcffc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
}