Preparation/DiceThrow.cpp at master · yukty2000/Preparation · GitHub

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
Leetcode
You have d dice, and each die has f faces numbered 1, 2, ..., f.
Return the number of possible ways (out of f^d total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Input: d = 1, f = 6, target = 3
Output: 1

Input: d = 2, f = 6, target = 7
Output: 6

Input: d = 30, f = 30, target = 500
Output: 222616187

*/


#define K 1000000007
typedef long long int lli;
class Solution {
public:

    int numRollsToTarget(int N, int M, int X) {
        int **Dp=(int **)malloc((N+1)*sizeof(int *));
        for(int i=0;i<=N;i++)
            Dp[i]=(int *)malloc((X+1)*sizeof(int));
        for(int i=0;i<=N;i++)
        {
            if(i==0)
                Dp[i][0]=1;
            else
                Dp[i][0]=0;
        }
        for(int i=1;i<=X;i++)
        {
            Dp[0][i]=0;
        }
        for(int i=1;i<=N;i++)
        {
            int iptr=0,jptr=-1;
            lli sum=0;
            for(int j=1;j<=X;j++)
            {
                jptr++;
                sum+=(lli)Dp[i-1][jptr];//(sum+(Dp[i-1][jptr])%K)%K;
                if(jptr-iptr+1>M)
                {
                    sum-=(lli)Dp[i-1][iptr];//(sum-(Dp[i-1][iptr])%K)%K;
                    iptr++;
                }
                Dp[i][j]=sum%K;
            }
        }
        int ans=Dp[N][X];
        for(int i=0;i<=N;i++)
            free(Dp[i]);
        free(Dp);
        return ans;
    }
};