是人都会做的简单题 - 面试题60. n个骰子的点数

n个骰子的点数

题目描述

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

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例：

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

提示：
1 <= n <= 11

转载来源：力扣（LeetCode）

题目分析

这是一道剑指Offer题集里的 简单 题，用一个简单的DP思路就可以简单的求解，而DP的状态转移方程也比较简单，很简单就推出来

• dp[ i ][ j ]记录的是 i 个 骰子总数是 j 的总情况数；
• 第 i 个骰子只能投出 1 - 6 这六种情况，而这六种情况的概率 显然 是dp[1][1-6]，都为1， i 个骰子总数是 j 的情况 显然 等于 sum( dp[ i - 1][ j - k ] * dp[ 1 ][ k ] )，其中 k 就是[1 , 6]，显然 乘号后面的可以去掉（都为1）；
• 这道 简单 题我显然只花了 40min 就完成了，过于 简单；

    public double[] twoSum(int n) {
        int[][] dp = new int[n + 1][6*n + 1];
        for(int i = 1; i <= 6; i++)
            dp[1][i] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = i; j <= n*6; j++){
                for(int k = 1; k <= 6 && k <= j-1; k++){
                    dp[i][j] += dp[i - 1][j-k];
                }
            }
        }
        double tmp = Math.pow(6,n);
        double[] result = new double[5*n + 1];
        for(int i = 0; i < 5*n + 1; i++){
            result[i] = dp[n][i+n] / tmp;
        }
        return result;
    }