有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。
请对每一枚硬币抛掷 一次，然后返回正面朝上的硬币数等于 target 的概率。
输入：prob = [0.4], target = 1
输出：0.40000
输入：prob = [0.5,0.5,0.5,0.5,0.5], target = 0
输出：0.03125
1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
如果答案与标准答案的误差在 10^-5 内，则被视为正确答案。
代码如下：
function fn(p, n) {
n = n === 0 ? p.length : n
n = n === 1 ? p.length - 1 : n
// p = [0.1, 0.5, 0.9]
// n = 1
// 方法一：直接模拟10万次，每次抛p.length个硬币，有n个朝上
let count = 100000
let result = 0
for (let i = count; i > 0; i--) {
let up = 0
p.forEach(it => {
if (it === 1) up++
else if (Math.random() <= it) up++
})
if (up === n) result++
}
console.log(result / count)
// 方法二：找出抛p.length个硬币，有n个朝上的组合，然后求和
var way = combine(p, n)
let hh = 0
way.forEach(it => {
let dd = 1
p.forEach(q => {
dd *= (it.includes(q) ? q : 1 - q)
})
hh += dd
})
console.log(hh)
// 方法三：动态规划，状态转义
let len = p.length
let dp = [1].concat(p).map(() => Array(n + 2).join(',').split('').map(() => 0))
dp[0][0] = 1
dp[0][-1] = 0
// i=0时，j从0到n, dp[0][j] = 0
for (let i = 1; i <= len; i++) {
for (let j = 0, max = Math.min(i, n); j <= max; j++) {
// 状态转移方程
dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1 - p[i-1])
}
}
console.log(dp[len][n])
}
function combine (list, num) {
let arr = arrange (list, num)
let maps = {}
let result = []
arr.forEach(it => {
it.sort()
if (!maps[JSON.stringify(it)]) {
maps[JSON.stringify(it)] = true
result.push(it)
}
})
return result
}
function arrange (list, num) {
if (num === 1) return list.map(it => [it])
else if (num < 1 || num > list.length) return []
// list = [1, 5, 3]
let result = []
let len1 = list.length
for (let i = 0; i < len1; i++) {
let cur = list[i]
let left = [].concat(list)
left.splice(i, 1)
let arr = arrange(left, num - 1)
for (let j = 0, len2 = arr.length; j < len2; j++) {
result.push([cur].concat(arr[j]))
}
}
return result
}