Proficient Level
Implement the countWaysToReachSumWithDice method that counts dice roll combinations that produce the target sum.
The input contains three integers: dice, faces, and target. Your task is to count how many ways the dice can be rolled so that their total sum is exactly target.
Each die has values from 1 to faces. Different dice orderings are counted as different ways. For example, with 2 dice and target 7, there are 6 possible combinations.
Example 1
Input
dice (int) =
2faces (int) =
6target (int) =
7Returns (int)
6Example 2
Input
dice (int) =
1faces (int) =
6target (int) =
3Returns (int)
1Example 3
Input
dice (int) =
2faces (int) =
6target (int) =
2Returns (int)
1Use dynamic programming where dp[d][s] stores how many ways to make sum s using d dice.
Start with dp[0][0] = 1, because there is one way to make sum zero with zero dice. Then for each die, try every possible face value and add the ways from the previous die count.
The final answer is the number of ways to make target using all dice.
Pseudocode:
function countWaysToReachSumWithDice(dice, faces, target):
dp = 2D array of dice + 1 by target + 1 filled with 0
dp[0][0] = 1
for d from 1 to dice:
for sum from 1 to target:
for face from 1 to faces:
if sum - face >= 0:
dp[d][sum] = dp[d][sum] + dp[d - 1][sum - face]
return dp[dice][target]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run