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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、 解法

• 数组内元素和为 1

• 要求每个和有多少种组合方式

• 每个组合方式数/总组合数就是概率了

func dicesProbability(_ n: Int) -> [Double] {
    let sRangeMin = n
    let sRangeMax = n * 6
    var total = 0
    var temp: [Int] = []
    var res: [Double] = []
    
    for s in sRangeMin...sRangeMax {
        let c = resultCount(of: s, by: n)
        total += c
        temp.append(c)
    }
    
    temp.forEach {
        res.append(Double($0) / Double(total))
    }
    
    return res
}

• 设 f(n,x) 为 n 个骰子和为 x 的组合数

• f(n,x) = f(n-1, x-1) + f(n-1, x-2) + f(n-1, x-3) + f(n-1, x-4) + f(n-1, x-5) + f(n-1, x-6)

var dp: [String : Int] = [:]

/// 求 n 个 1-6 的数字和为 num 的组合数
/// - Parameters:
///   - num: -
///   - n: -
/// - Returns: 组合数
func resultCount(of num: Int, by n: Int) -> Int {
    guard num >= n, num <= n*6 else { // 注意控制边界条件
        return 0
    }
    
    guard n > 1 else {
        return 1
    }
    
    let key = "\(n) - \(num)"
    if let r = dp[key] {
        return r
    }
    
    var res: Int = 0
    for i in 1...6 {
        res += resultCount(of: num - i, by: n - 1)
    }
    
    dp[key] = res
    return res
}