Dice Throw

• Time : $O(A * C * B)$
• Space : $O(A * C)$

c++

long long dp[1010][1010];
long long mod = 1e9 + 7;
long long helper(int d, int ma, int c) {
    if(c < 0) return 0;
    if(dp[d][c] != -1) return dp[d][c];
    if(d <= 0) return 0;
    long long& res = dp[d][c] = 0;
    for(int i = 1; i <= min(ma,c - d + 1); i++) {
        res = (res + helper(d-1,ma,c-i)) % mod;
    }
    return res;
}
int Solution::findDiceSum(int A, int B, int C) {
    memset(dp, -1, sizeof dp);
    dp[0][0] = 1;
    return helper(A,B,C);
}