面试题60(剑指offer)--n个骰子的点数

题目：

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

示例：

输入：
n = 2
输出：
{[2,0.03],[3,0.06],[4,0.08],[5,0.11]
,[6,0.14],[7,0.17],[8,0.14],[9,0.11]
,[10,0.08],[11,0.06],[12,0.03]}

解法：

    /**
     * 动态规划规律：f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6)
     * 向已有的骰子中再加入一个骰子，此时和为n出现的次数应为和为n-1,
     * n-2,n-3,n-4,n-5,n-6的次数之和
     * @param n
     * @return
     */
    public static Map<Integer, Double> dicesSum(int n) {
        Map<Integer, Double> resMap = new HashMap<>();
        int[] resA = new int[6 * n + 1];
        int[] resB = new int[6 * n + 1];
        for (int i = 1; i <= 6; i++) {
            resA[i] = 1;
        }
        boolean flag = false;//flag用于标识两个数组的交换
        if (n > 1) {
            for (int j = 2; j <= n; j++) {
                if (!flag) {
                    for (int k = j; k <= 6 * j; k++) {
                        resB[k] = f(k, resA);
                    }
                    flag = true;
                } else {
                    for (int k = j; k <= 6 * j; k++) {
                        resA[k] = f(k, resB);
                    }
                    flag = false;
                }
            }
        }
        if (!flag) {
            for (int i = n; i <= 6 * n; i++) {
                resMap.put(i, ratio(resA[i], n));
            }
        } else {
            for (int i = n; i <= 6 * n; i++) {
                resMap.put(i, ratio(resB[i], n));
            }
        }
        return resMap;
    }

    /**
     * 计算次数所占比例
     * @param i 对应情况发生次数
     * @param n 可能发生情况综述
     * @return
     */
    private static Double ratio(int i, int n) {
        return i / Math.pow(6, n);
    }

    /**
     * 计算当前点数发生的次数
     * @param k
     * @param res
     * @return
     */
    private static int f(int k, int[] res) {
        int temp = 0;
        for (int i = k - 1; i >= k - 6; i--) {
            if (i > 0) {
                temp = temp + res[i];
            }
        }
        return temp;
    }