题目链接

Lintcode

题目描述

把 n 个骰子扔在地上，求点数和为 s 的概率。

解题思路

动态规划，dp[i][j]表示第i个骰子得到j点数的总次数

public class Solution {
   
    /** * @param n an integer * @return a list of Map.Entry<sum, probability> */
    public List<Map.Entry<Integer, Double>> dicesSum(int n) {
   
        final int face = 6;
        final int pointNum = face * n;
        long[][] dp = new long[n+1][pointNum+1];
        for (int i=1;i<=face;i++)
            dp[1][i] = 1;
        for (int i=2;i<=n;i++) {
   
            for (int j=i;j<=i*face;j++) {
   
                for (int k=1;k<=j && k<=face;k++)
                    dp[i][j] += dp[i-1][j-k];
            }
        }
        List<Map.Entry<Integer, Double>> res = new ArrayList<>();
        double totalNum = Math.pow(face, n);
        for (int i=n;i<=pointNum;i++) 
            res.add(new AbstractMap.SimpleEntry<>(i, dp[n][i]/totalNum));
        return res;
    }
}