Picking Up the Dice

This problem gives us a dice roll of k dice, and asks how many/which we should re-roll to have the best chance of summing to a given t.

In this case, there are two parts to the problem:

1) we only have 24 dice, so it should be a major hint that there is a brute force step. We can easily iterate over all 2^24 choices of rerolling dice. 2) for each option, we have to compute the chance of rolling t. Computing this each time is too slow, but we can use a relatively straightforward DP to get the chances of using n dice to roll exactly m. It works as follows:

dp[n][m] = count of ways of rolling exactly m with n dice. We add once dice at a time, and for each possible roll for that dice, and each possible previous total, we add to the row. The relation is:

dp[dice_number][roll+previous_dice_sum]+=dp[dice_number-1][previous_dice_sum]. We apply this for all dice, all rolls, and all previous dice sums.

The base case is that dp[0][0] = 1, or, there is 1 way to roll 0 with 0 dice.

Once we are done, we can divide each entry by the sum of that row to get a probability (6 for 1 dice, 6^2 for 2...etc). If this method is used, we must be very careful, as the tolerances when dividing by 6^24 are incredibly small, meaning epsilon when comparing the doubles for equality (when computing the max), must be tiny. In reality, one should use rational math, and compare the fractions directly, instead of using floating point division (even with doubles). This ensures there will not be issues.