DP笔记(4)：概率 DP之抛掷硬币、

抛掷硬币

有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。请对每一枚硬币抛掷 一次，然后返回正面朝上的硬币数等于 target 的概率。

示例 1：  输入：prob = [0.4],                          target = 1     输出：0.40000

示例 2：  输入：prob = [0.5,0.5,0.5,0.5,0.5]    target = 0     输出：0.03125 

如果概率都一样（1/2）,推荐阅读《几道抛硬币问题》各种情况都包括了，但是此题 每枚硬币正面朝上的概率可能都是不同的（事先预设的）

解题思路

用传统的排列组合方法来做的，因为我们在手算的时候也是这样，先从n个硬币中选target 个，让他们为正面，其他为反面，将概率相乘；最后将所有可能的组合相加起来。但是这样做的话会超时。

虽然咋一看这道题跟不是求最优化的，貌似跟动态规划风马牛不相及，但其实仔细一想我们在用解法1的时候 其实是有很多重复计算在里面的，这倒是跟动态规划有关了。

动态规划五部曲

假设已知抛i - 1个硬币有j个向上的概率，那么在抛第i个硬币的时候，还是j个向上的概率就是第i 个硬币是向下的(1 - p)；那么j + 1个向上的概率就是第i个硬币是向上的(p)。 但是我们要知道抛i次有j次向上的组合是有多种的，而最后的概率是这些组合各自的概率的相加，因此 状态转移方程是 += 而不是 = 此外，我们初始化状态矩阵为全0，且dp[0][0]为1，因为抛0次只能有0个向上，概率为1

我们最后得到的状态矩阵是每一行的和都为1，因为每一行代表了抛i次，而抛i次的情况下共有0 ~ i个 向上的可能，这些概率加起来的和为1，而i+1以后的概率都为0. 也就是说我们最后得到的矩阵是一个下三角矩阵 (对角线以上的元素都为0)

状态矩阵

状态矩阵：dp[i][j]表示抛i个硬币，有j个向上的概率 状态转移方程：

dp[i][j + 1] += dp[i - 1][j] * p
dp[i][j] += dp[i - 1][j] * (1 - p)

最终代码：

function probabilityOfHeads(prob, target) {
  if (target === 0) {// 这里对0个向上的情况特殊考虑，因为这个case的计算简单，没必要通过dp，仅仅是为了加速
    let ans = 1;
    for (let p of prob) ans *= (1 - p);
    return ans;
  }
  const length = prob.length,dp = Array.from({length:length+1},() => new Array(length+1).fill(0));
  dp[0][0] = 1;//  抛0次的话只能有0个为正

  for (let i = 1; i <= length; i++) {
    const p = prob[i - 1];
    for (let j = 0; j < i; j++) {//抛i次硬币可能会有0, 1, 2, ..., i - 1, i个向上，因此都需要计算
      dp[i][j] += dp[i - 1][j] * (1 - p);//注意这里状态转移方程是 += ，不是 =
      dp[i][j + 1] += dp[i - 1][j] * p;
    }
  }
  return dp[prob.length][target];//最后抛n次，有target个向上的概率就是我们要的
}

参考文章：

https://sysujayce.github.io/posts/tosscoin/

转载本站文章《DP笔记(4)：概率 DP之抛掷硬币、》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9145.html