406 字
2 分钟
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}