剑指 Offer 60. n个骰子的点数

一、题目描述

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

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

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:

输入: 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

二：题目难度：中等

三、题解

方法一：回溯

时间复杂度：O(6^n)

空间复杂度：O(n)

class Solution {
    HashMap<Integer,Integer> mp = new HashMap<>();
    int number;
    int pointSum = 0;public double[] dicesProbability(int n) {
        number = n;
        countPoint(1);
        double[] res = new double[mp.size()];
        // for(Map.Entry<Integer, Integer> entry : mp.entrySet()){
        //     System.out.println(entry.getKey()+" "+entry.getValue());
        // }
        int pos = 0;
        int sum = 0;
        for(Integer value : mp.values()){
            sum += value;
        }
        for(Integer value : mp.values()){
            res[pos] = value*1.0/sum;
            pos++;
        }
        return res;
    }
    public void countPoint(int i){
        if(i==number+1){
            mp.put(pointSum,mp.getOrDefault(pointSum,0)+1);
            return;
        }
        for(int s = 1;s<=6;s++){
            pointSum += s;
            countPoint(i+1);
            pointSum -= s;
        }
    }
}

但是n=11的时候会超时。

 方法二：动态规划

时间复杂度：O(n^2)

空间复杂度：O(n^2)

dp[i][j]表示：第i个骰子出现和为j的次数

dp[i][j] = dp[i-1][j-k](k = 1,2,3,...,6)

边界值：dp[1][j] = 1;  (j = 1,2,3,...,6)

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<vector<int> > dp(n+1,vector<int>(6*(n+1)));
        for(int j=1;j<=6;j++)
            dp[1][j] = 1;
        for(int i = 2;i<=n;i++){
            for(int j = i;j<=6*i;j++){
                for(int k=1;k<=6;k++){
                    if(j-k<=0)
                        break;
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        int sum = pow(6.0,n);
        vector<double> ret;
        for(int i = n;i<=6*n;i++){
            ret.emplace_back(dp[n][i]*1.0/sum);
        }
        return ret;
    }
};