Lecture 106:- Number Of Dice Roll With Target Sum

The "Number of Dice Rolls With Target Sum" problem is a classic dynamic programming problem. Given the number of dice d, the number of faces on each die f, and a target sum target, you need to find the number of ways to roll the dice to get the target sum.

Here's a Python function that implements the Number of Dice Rolls With Target Sum algorithm using dynamic programming:

pythonCopy code

def num_dice_rolls(d, f, target):    MOD = 10**9 + 7    dp = [[0] * (target + 1) for _ in range(d + 1)]    dp[0][0] = 1    for i in range(1, d + 1):        for j in range(1, target + 1):            for k in range(1, min(f, j) + 1):                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD    return dp[d][target] # Test the function print(num_dice_rolls(2, 6, 7))   # Output: 6 (Possible combinations: [1, 6], [2, 5], [3, 4], [4, 3], [5, 2], [6, 1]) print(num_dice_rolls(2, 6, 12))  # Output: 1 (Only one combination: [6, 6]) print(num_dice_rolls(3, 4, 5))   # Output: 6 (Possible combinations: [1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1])

In this code, the num_dice_rolls() function takes the number of dice d, the number of faces on each die f, and the target sum target as input.

The dynamic programming approach uses a 2D array dp to store the number of ways to roll the dice to get each possible sum from 0 to the target. The entry dp[i][j] represents the number of ways to get the sum j using i dice.

The algorithm iteratively fills the dp array based on the recurrence relation. For each additional die, it calculates the number of ways to get each possible sum by considering the possible outcomes of rolling the current die.

The result is stored in dp[d][target], which represents the number of ways to roll the dice to get the target sum. The time complexity of this solution is O(d * f * target), where d is the number of dice, f is the number of faces on each die, and target is the target sum. The space complexity is also O(d * target) due to the dynamic programming array dp.