## [兩個盒子中球的顏色數相同的概率](https://leetcode-cn.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/) #### 思路 根據Hard必死定律，周賽沒做出來，繼續拜讀大佬解題 **閱讀理解** * 這道題的中文翻譯稍微有點容易出現誤解，還是需要多讀幾遍理解意思 * 大概意思是：有兩個盒子，需要把球隨機的放到這兩個盒子當中 * 最后計算兩個盒子中顏色數相同情況的概率 * 題目要求 `請計算「兩個盒子中球的顏色數相同」的情況的概率。`，比如說盒子1有3種顏色，盒子2也有三種顏色，不管顏色是什么。 這種情況都是符合條件的 **分析** * 所有的可能性，就是全排列的組合數，如下：（圖片來自[huahua](https://space.bilibili.com/9880352?from=search&seid=1276580199457930821)大佬，我是[huahua](https://space.bilibili.com/9880352?from=search&seid=1276580199457930821)大佬的小迷弟，大家可以關注一波） 對于示例2，應該有`$ 4! $`種可能性，但是1，2重復，這邊需要去重，一共就為12中可能，如上圖。全排列+去重，聯想到 [47\. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)。 * 可以取出全排列的數量，然后在除以相同顏色的數量階乘乘積，得到去重之后的排列組合數。 * 接著從中遍歷出滿足題目要求的，顏色數量相同的情況，進行比較得出答案 不出意外的TLE（苦），偶然發現 [國際版暴力解法](https://leetcode-cn.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/solution/zhuan-ge-guo-ji-ban-ben-de-bao-li-jie-fa-you-mei-d/)，居然可以AC！而且代碼非常簡潔，大佬牛批！ #### 代碼 python3 ``` class Solution: def multinomial(self, n): return factorial(sum(n))/prod([factorial(i) for i in n]) def getProbability(self, balls): k, n, Q = len(balls), sum(balls)// 2, 0 arrays = [range(0,i+1) for i in balls] t = list(product(*arrays)) for i in range(len(t)): if sum(t[i]) == n and t[i].count(0) == t[-i-1].count(0): Q += self.multinomial(t[i]) * self.multinomial(t[-i-1]) return Q / self.multinomial(list(balls)) ``` 本題TLE優化方案，可以使用**動態規劃**進行求解。dp正在研究中，大家請耐心等待（菜雞的掙扎） 未完待續。。。