跳到主要内容

硬币问题

抛掷硬币​

有一些不规则的硬币。在这些硬币中，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. 状态定义: dp[i][j]表示从0到第i枚硬币，正面朝上个数等于j的概率
  2. 状态转移方程:抛第i枚硬币，要么朝上，朝下两种状态
    • 第i枚朝上时: dp[i][j]=dp[i-1][j-1]*prob[i-1]
    • 第i枚朝下时: dp[i][j]=dp[i-1][j]*(1-prob[i-1])
    • 结合两种状态可得: dp[i][j]=dp[i-1][j-1]*prob[i-1]+dp[i-1][j]*(1-prob[i-1])
  3. 初始化状态:
    • dp[0][0] 为1
    • 当target为0时，即j=0时，dp[i][0]=dp[i-1][0]*(1-prob[i-1])
  4. 问题答案:

:::details 点击查看代码

function probabilityOfHeads(prob, target) {
    const len=prob.length;
    const dp=new Array(len+1).fill(0).map(()=>new Array(target+1).fill(0));
    dp[0][0]=1;
    for(let i=1;i<=len;i++){
        dp[i][0]=dp[i-1][0]*(1-prob[i-1])
    }
    for(let i=1;i<=len;i++){
        for(let j=1;j<=target;j++){
            dp[i][j]=dp[i-1][j-1]*prob[i-1]+dp[i-1][j]*(1-prob[i-1])
        }
    }
    return dp[len][target];
};

:::

性能分析: