Number of Dice Rolls With Target Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
#define MOD 1000000007
4
  int dp[32][1002];
5

6
  int solve(int d, int f, int target) {
7
    if (d == 0 && target == 0) return 1;
8
    if (d <= 0 || target <= 0) return 0;
9
    if (dp[d][target] != -1) return dp[d][target];
10

11
    int sum = 0;
12
    for (int i = 1; i <= f; i++) {
13
      sum = (sum % MOD + solve(d - 1, f, target - i) % MOD) % MOD;
14
    }
15
    dp[d][target] = sum;
16
    return dp[d][target];
17
  }
18

19
  int numRollsToTarget(int d, int f, int target) {
20
    memset(dp, -1, sizeof(dp));
21
    return solve(d, f, target);
22
  }
23
};