Dice Throw - Amazon Top Interview Questions

                        Solution in C++ :

const int MOD = 1e9 + 7;

int solve(int n, int faces, int total) {
    vector<int> dp(total + 1);
    for (int i = 1; i <= min(faces, total); ++i) dp[i] = 1;
    vector<int> pre(total + 1);
    for (int turn = 2; turn <= n; ++turn) {
        for (int i = 1; i <= total; ++i) pre[i] = (pre[i - 1] + dp[i]) % MOD;
        for (int i = 1; i <= total; ++i) {
            int l = max(0, i - faces - 1);
            dp[i] = (pre[i - 1] - pre[l] + MOD) % MOD;
        }
    }
    return dp[total];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    int[][] dp;
    int mod = (int) 1e9 + 7;
    public int solve(int n, int faces, int total) {
        dp = new int[n + 1][total + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return solve_(n, faces, total, 0);
    }
    public int solve_(int n, int faces, int total, int sum) {
        if (n == 0 && total == sum) {
            return 1;
        }

        if (n < 0 || sum > total) {
            return 0;
        }

        if (dp[n][sum] != -1) {
            return dp[n][sum];
        }
        int count = 0;

        for (int i = 1; i <= faces; i++) {
            count += solve_(n - 1, faces, total, sum + i) % mod;
            count %= mod;
        }
        return dp[n][sum] = count;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, n, faces, total):
        if total < n:
            return 0

        if total > n * faces:
            return 0

        previous = [1]

        for i in range(n):
            max = min(len(previous) + faces, total + 1)
            current = []
            running = 0
            for j in range(max):
                current.append(running)
                if j < len(previous):
                    running += previous[j]
                if j >= faces:
                    running -= previous[j - faces]
            previous = current

        return current[total] % (10 ** 9 + 7)