aboutsummaryrefslogtreecommitdiff
path: root/num_dice_roll_target_sum.cpp
blob: abb7596137f560b543569d5fad72be2bc6506e3f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "leetcode.h"

class Solution {
public:
  int numRollsToTarget(int n, int k, int target) {
    int mod = 1000000007;
    vvd dp(n + 1, vector<int>(target + 1, 0));
    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 (x <= j)
            dp[i][j] = ((dp[i][j] % mod) + (dp[i - 1][j - x] % mod)) % mod;
    return dp[n][target];
  }
};

int main() {
  Solution obj;
  cout << obj.numRollsToTarget(1, 6, 3);
}