Dices Sum 20

Question

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.

Example

Given n = 1, return [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]].

Solution

用dp解决。dp[i][j]表示i个骰子一共得到j点的概率。要得到dp[i][j]可以考虑若最后一个筛子的点数为k（1~6），则前i－1个筛子一共得到的点数为j-k（因为i-1个筛子至少得到i-1点，所以j-k >= i - 1 => k <= j - i + 1）。所以只要把最后一个筛子为k的各种情况加起来最后再除以6即可（每多一个筛子概率要多除以一个6）。

状态函数：

dp[i][j] = dp[i-1][j-k] (i <= j <= 6 * i, k >= 1 && k <= j - i + 1 && k <= 6)

代码如下：

public class Solution {
    /**
     * @param n an integer
     * @return a list of Map.Entry<sum, probability>
     */
    public List<Map.Entry<Integer, Double>> dicesSum(int n) {
        // Write your code here
        // Ps. new AbstractMap.SimpleEntry<Integer, Double>(sum, pro)
        // to create the pair
        List<Map.Entry<Integer, Double>> result = new ArrayList<Map.Entry<Integer, Double>>();
        if(n < 1){
            return result;
        }
        //初始化n＝1的情况
        double[][] matrix = new double[n + 1][6 * n + 1];
        for(int i = 1; i <= 6; i++){
            matrix[1][i] = 1.0/6;
        }

        for(int i = 2; i <= n; i++){
        //i个筛子至少得到i点，至多得到6 * i点
            for(int j = i; j <= 6 * i; j++){
            //k表示最后一个筛子能取的点数
                for(int k = 1; k <= 6; k++){
                    if(k <= j - i + 1){
                        matrix[i][j] += matrix[i - 1][j - k];
                    }
                }
                //相对i－1个筛子多了一个筛子，因此加和的每一项都要除以6
                matrix[i][j] /= 6.0;
            }
        }

        for(int i = n; i <= 6 * n; i++){
            result.add(new AbstractMap.SimpleEntry<Integer, Double>(i, matrix[n][i]));
        }

        return result;
    }
}