LeetCode 1230. 抛掷硬币
题目描述
题意分析
给定每枚硬币正面朝上的概率，每枚独立抛掷一次，求最后恰好出现
target次正面的概率。不同硬币的正面概率可以不同，不能统一当作公平硬币处理。目标是精确的正面次数，不是至少或至多。所有硬币都要处理，即使已经出现目标数量的正面，剩余硬币仍必须全部反面，才属于这个结果。
解法：概率 DP
核心思路
[!blue]
定义
dp[j]为已经处理的这些硬币中，恰好出现j次正面的概率。尚未抛硬币时，零次正面必然发生，所以dp[0] = 1，其他次数的概率为零。处理正面概率为
p的下一枚硬币后，要得到j次正面只有两种来源：之前已有j次，这次抛反面；或者之前有j - 1次，这次抛正面。两种情况按当前硬币的结果划分，互不重叠，因此概率相加；当前硬币与之前独立，因此每条来源的联合概率相乘。转移为new[j] = old[j] * (1 - p) + old[j - 1] * p。压缩成一维后，从大到小更新
j，这样原位置的dp[j]和左侧较小位置dp[j - 1]都还没有在本轮改写，仍属于上一批硬币。若从小到大更新，就会让较高正面次数读取本轮的新结果，相当于错误重复使用当前硬币。零次正面没有“之前负一次”的来源，只能由之前零次且本次反面得到，所以单独执行
dp[0] *= 1 - p。它必须放在其他状态更新之后，避免dp[1]读取到本轮已经变化的零次概率。只需保留从零到
target的状态。已经超过目标的正面次数不会在以后减少，因此不会再贡献目标答案，丢弃它们是安全的；保留状态的概率之和可能小于一，不应额外归一化。处理全部硬币后，返回dp[target]。
解题步骤
- 创建
target + 1项浮点数组，初始化dp[0] = 1。- 依次读取每枚硬币的正面概率
p。- 从
heads = target到一倒序更新反面和正面两种来源的概率和。- 最后将
dp[0]乘以1 - p。- 全部处理后返回
dp[target]；目标为零时只累计所有反面概率。
代码实现
class Solution {
public double probabilityOfHeads(double[] prob, int target) {
double[] dp = new double[target + 1];
// 尚未抛任何硬币时，零正面的概率为一。
dp[0] = 1.0;
for (double p : prob) {
// 倒序更新，确保较少正面的来源仍是上一轮状态。
for (int heads = target; heads >= 1; heads--) {
dp[heads] = dp[heads] * (1.0 - p) + dp[heads - 1] * p;
}
// 零正面只能来自本次反面，最后更新避免污染其他来源。
dp[0] *= 1.0 - p;
}
return dp[target];
}
}
func probabilityOfHeads(prob []float64, target int) float64 {
dp := make([]float64, target+1)
// 尚未抛任何硬币时，零正面的概率为一。
dp[0] = 1.0
for _, p := range prob {
// 倒序更新，确保较少正面的来源仍是上一轮状态。
for heads := target; heads >= 1; heads-- {
dp[heads] = dp[heads]*(1.0-p) + dp[heads-1]*p
}
// 零正面只能来自本次反面，最后更新避免污染其他来源。
dp[0] *= 1.0 - p
}
return dp[target]
}
复杂度分析
- 时间复杂度：$O(n(target+1))$，每枚硬币更新全部保留状态；
target = 0时也仍需扫描全部概率。- 空间复杂度：$O(target+1)$，保存一行概率状态，不需要完整的按硬币数展开的二维表。
关键点总结
[!green]
- 两种来源互斥，所以相加；当前硬币与历史独立，所以各自乘以本次结果概率。
- 原地更新必须读取上一轮状态，倒序及最后更新零次状态共同保证这一点。
- 精确次数超过目标后不会减少，可以舍弃这些状态，但不能重新归一化剩余概率。
易错点总结
[!yellow]
- 从小到大更新，会混入本轮已更新的前驱概率，重复使用同一枚硬币的信息。
- 先更新
dp[0]，会污染随后dp[1]所需的上一轮零次概率。- 忘记反面概率
1 - p，无法正确处理不增加正面数的情况，目标为零时尤其明显。- 把初始
dp[0]设为零，会使所有转移都失去概率来源。- 达到目标正面数后提前停止处理剩余硬币，计算的是其他事件，而不是全部硬币恰好出现目标次正面。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1155. 掷骰子等于目标和的方法数 | 中等 | 同样按已处理次数和目标结果推进DP，本题转移乘各硬币的概率，原题对等价走法计数。 |
| 494. 目标和 | 中等 | 每个对象都做二选一，本题按概率加权，原题每个有效方案按1累加。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！