Lintcode20 Dices Sum solution problem solution

[topic description]

Throw n dices, the sum of the dices' faces is S. Given n, find the all possible value of S along with its probability.

Notice:You do not care about the accuracy of the result, we will help you to output results.

Throw n dice and the sum of the numbers above is S. Given Given n, list all possible S values and their corresponding probabilities.

Note: you do not need to pay attention to the accuracy of the answer, we will help you output the answer

[topic link]

Http://www.lintcode.com/en/problem/dices-sum/

[topic Analysis]

It feels more intuitive to use dfs to do this, but it can't pass time cost. In dp's way, here's what I think:

Use dp [I] [j] to denote the number of times that the sum is j in the case of I + 1 dice. So intialize, the dp [0] [j], j = 1. 6 all have values of 1, and then cycle from I = 1. The difference between I dice and I + 1 dice is 1 dice (nonsense), so use another k = 1. 6 to traverse, then the number of times I + 1 dice is rolled to j + k is the number of times dp [I] [j + k] plus dp [I-1] [j].

In this way, we find the number of times dp [n-1] [j], j = n. 6 * n for each S in the case of n dice. Then the probability is each dp [n-1] [j] divided by the total number of occurrences sum (DP [n-1] [j]).

Note here that the value of dp can be very large, so use long long, otherwise there will be a negative answer in the case of some test case (e.g.n = 15).

[answer link]

Http://www.jiuzhang.com/solution/dices-sum/