Number of Dice Rolls With Target Sum

Problem Statement:

You have n dice, and each dice has k faces numbered from 1 to k. Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1, k = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.

Example 2:

Input: n = 2, k = 6, target = 7 Output: 6 Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: n = 30, k = 30, target = 500 Output: 222616187 Explanation: The answer must be returned modulo 109 + 7.

Constraints:

• 1 <= n, k <= 30
• 1 <= target <= 1000

Solution:

1.Recursion

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        int[] ans = new int[1];
        int[][] dp = new int[n + 1][target + 1];
        for(int[] row: dp){
            Arrays.fill(row, -1);
        }
        numRollsToTargetHelper(n, k, target, ans, dp);
        return ans[0];
    }
 
    public void numRollsToTargetHelper(int currDice, int k, int target, int[] ans, int[][] dp) {
        if (currDice == 0) {
            if (target == 0) {
                ans[0] = (ans[0] + 1) % 1000000007;
                dp[currDice][target] = ans[0];
            }
            return;
        }
 
        if (target < 0) {
            return;
        }
 
        if(dp[currDice][target] != -1){
            return;
        }
 
        for (int i = 1; i <= k; i++) {
            numRollsToTargetHelper(currDice - 1, k, target - i, ans, dp);
        }
    }
}

2. Recursion and Memoization:

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        for(int[] row: dp){
            Arrays.fill(row, -1);
        }
        return numRollsToTargetHelper(n, k, target, dp);
    }
 
    public int numRollsToTargetHelper(int currDice, int k, int target, int[][] dp) {
        if (currDice == 0) {
            if (target == 0) {
                return 1;
            }
            return 0;
        }
        if(target < 0){
            return 0;
        }
 
        if (dp[currDice][target] != -1) {
            return dp[currDice][target];
        }
        
        int ways = 0;
        for (int i = 1; i <= k; i++) {
            ways = (ways + numRollsToTargetHelper(currDice - 1, k, target - i, dp)) % 1000000007;
        }
        
        return dp[currDice][target] = ways;
    }
}

3. Tabulation:

public int numRollsToTarget(int n, int k, int target) {
    int[][] dp = new int[n + 1][target + 1];
    dp[0][0] = 1;  // There is one way to achieve a sum of 0 with 0 dice
 
    int MOD = 1000000007;
 
    for (int dice = 1; dice <= n; dice++) {
        for (int t = 0; t <= target; t++) {
            dp[dice][t] = 0;  // Initialize current state
            for (int face = 1; face <= k; face++) {
                if (t - face >= 0) {
                    dp[dice][t] = (dp[dice][t] + dp[dice - 1][t - face]) % MOD;
                }
            }
        }
    }
 
    return dp[n][target];
}

4. Space Optimized:

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        int[] prev = new int[target + 1];
        int[] curr = new int[target + 1];
        prev[0] = 1;// There is one way to achieve a sum of 0 with 0 dice
 
        int MOD = 1000000007;
 
        for (int dice = 1; dice <= n; dice++) {
            for (int t = 0; t <= target; t++) {
                curr[t] = 0;
                for (int face = 1; face <= k; face++) {
                    if (t - face >= 0) {
                        curr[t] = (curr[t] + prev[t - face]) % MOD;
                    }
                }
            }
            prev = curr.clone();
        }
 
        return prev[target];
    }
}