題目描述

把 n 個骰子扔在地上，所有骰子朝上一面的點數之和為 s。輸入 n，打印出 s 的所有可能的值出現的概率。

你需要用一個浮點數數組返回答案，其中第 i 個元素代表這 n 個骰子所能擲出的點數集合中第 i 小的那個的概率。

• 1 <= n <= 11

題目樣例

示例

• 輸入: 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 個骰子的概率推導出 n+1 個骰子的概率嗎

解決方案

思路

• 分析題目, 先從 1 個骰子的最簡單情況出發, 顯然點數為 1~6 的概率都是 1/6
• 那如果是 2 個骰子呢? 假設第一個骰子點數為 1, 第二個可以是 1~6, 兩者之和就是 2~7; 而如果第一個點數為 2, 那么兩者之和就是 3~8, 以此類推
• 顯然 2 個骰子點數之和為 2 的概率是                         (1/6)*(1/6)=1/36, 只有 1+1 一種情況; 而點數之和為 3 的概率是                         1/36+1/36=1/18, 有 1+2 和 2+1 兩種情況, 以此類推
• 所以如果我們使用一個字典來保存當前骰子數 n 的每個點數之和的概率, 即鍵值對是                         {點數和:概率}, 那么對于 n+1 而言, 我們只需要對每個點數之和加上 1~6 作為新的點數之和, 將原有概率乘以 1/6 累加到新的點數和對應的概率上即可
• 最后只需要根據有效點數之和從小到大, 將字典中的值依次存入最終結果中
• 對于 n 個骰子而言, 其點數之和最小為 n (每個骰子點數都是 1), 最大為                         6*n (每個骰子點數都是 6)
• 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(N^2): 兩層循環, 外層遍歷 N 個數, 內層遍歷                         5N*6 個數
• 空間復雜度 O(N): 字典中需要存 5N 個鍵值對

代碼

import collections


class Solution:
    def twoSum(self, n: int) -> List[float]:
        # DP, dp為當前的點數和=>概率的字典, 初始化dp[0] = 1, 代表0個骰子時點數之和為0的概率為1
        # 增加一個骰子后, 我們只需要對原來字典的每個點數之和加上 1~6 作為新的點數之和, 并將原有概率乘以 1/6 累加到新的點數和對應的概率上即可
        dp = {}
        dp[0] = 1
        for i in range(1, n + 1):
            newdp = collections.defaultdict(int)
            for sm in dp:
                for v in range(1, 7):
                    # 增加一個骰子后, 累加其概率到新的點數和上
                    newdp[sm + v] += dp[sm] / 6
            dp = newdp
        res = []
        for sm in range(n, 6 * n + 1):
            # 將值依次存入結果中
            res.append(dp[sm])
        return res