LeetCode 1230. 抛掷硬币

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节跳动
标签
数组 动态规划 数学 概率与统计
目录

题目描述

✅ 1230. 抛掷硬币

题意分析

有 n 枚硬币，第 i 枚正面朝上的概率是 prob[i]，各枚硬币相互独立且每枚只抛一次。要求恰好出现 target 次正面的概率。

「恰好」两个字排除了前缀和式的累积统计，答案是一个点概率而不是尾概率。「每枚只抛一次」意味着每枚硬币对结果的贡献是二选一的：要么贡献一次正面，要么贡献零次——这是一个每件物品选或不选、且两种选择各自带权的结构。

数据规模是 prob.length 最多 1000、target 不超过 prob.length，乘积在百万量级，这个规模明确指向一个二维规模的递推，而不是指数级枚举，也不是闭式公式（各枚硬币概率不同，无法套二项分布）。

注意概率可以取到 0 和 1 的极端值，也就是说存在「必然反面」和「必然正面」的硬币，正确的写法应当自然覆盖这两种情况而不需要特判。

边界：target 为 0（要求全反面）、target 等于硬币总数（要求全正面）、某枚硬币概率为 0 或 1、只有一枚硬币。

解法：概率 DP

核心思路

枚举每枚硬币的正反面共有 $2^n$ 种结果，但答案只关心正面个数。将“具体哪些硬币为正面”合并成同一个计数状态，就得到概率动态规划。

定义 dp[j]：处理完当前前缀的硬币后，恰好出现 j 次正面的概率，只保留 0 <= j <= target。处理一枚正面概率为 p 的硬币时，新状态有两个互斥来源：此前已有 j 次正面且本次为反面，或此前有 j - 1 次正面且本次为正面：

newDp[j] = dp[j] × (1 - p) + dp[j - 1] × p。

初始 dp[0] = 1，表示尚未抛硬币时，出现 0 次正面是必然事件。状态只依赖上一轮，可原地更新；为保证 dp[j - 1] 仍是上一轮的值，j 必须从大到小遍历。dp[0] 没有第二个来源，在最后单独乘以 1 - p。

循环不变量是：处理完前 i 枚硬币后，dp[j] 精确等于其中恰有 j 次正面的概率。数组截断到 target 后，超出 target 的概率质量会被丢弃，因此这些状态之和不一定为 1，但不会影响目标状态。

正确性说明：初始状态显然成立。假设不变量在处理当前硬币前成立，转移枚举了得到 j 次正面的全部且互斥的两种情况，并按独立事件乘法、互斥事件加法计算概率，所以更新后仍成立。倒序保证每种来源都来自上一轮，每枚硬币恰使用一次。归纳到全部硬币后，dp[target] 就是所求概率。

解题步骤

  • 创建长度 target + 1 的数组，并令 dp[0] = 1。
  • 依次处理每枚硬币的正面概率 p。
  • 对 j = target, target - 1, ..., 1，按两种来源更新 dp[j]。
  • 更新 dp[0] = dp[0] × (1 - p)。
  • 所有硬币处理完后返回 dp[target]。

prob = [0.5,0.5,0.5]、target = 2 时，三轮后的 dp[2] = 0.375。target = 0 时状态只保留全反面的连乘；target = n 时只保留全正面的路径。概率为 0 或 1 的硬币也由同一转移自然处理。

代码实现

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 \times (target + 1))$。每枚硬币更新从 0 到 target 的状态，通常简写为 $O(n \times target)$。
  • 空间复杂度：$O(target + 1)$。一维数组原地滚动保存所需状态。

关键点总结

  • 状态只记录正面个数，合并了具体硬币组合这一无关信息。
  • 一维转移必须倒序，确保读取的 dp[heads - 1] 尚未被当前硬币更新。
  • dp[0] 只有“当前硬币为反面”一个来源，要在倒序循环后单独更新。
  • 截断状态后概率和可能小于 1；不应把“总和恒为 1”当作滚动数组的断言。

易错点总结

  • 正序更新状态：prob = [0.5,0.5]、target = 2 会得到 0.375，而正确概率是 0.25，因为同一枚硬币在一轮内被重复使用。
  • 漏掉 dp[0] 更新：prob = [0.5,0.5]、target = 0 会错误返回 1，正确答案是 0.25。
  • 先更新 dp[0] 再更新其他状态：prob = [0.5,0.5]、target = 1 会得到 0.25，正确答案是 0.5，因为 dp[1] 读到了本轮的新 dp[0]。
  • 交换正反概率因子：prob = [1.0]、target = 1 会返回 0，而正确答案是 1。
  • 初始化 dp[0] = 0：所有后续状态都没有概率来源，任何非零答案都会被算成 0。
  • 使用 float 累积：长输入中的舍入误差更明显；Java 和 Go 都应使用双精度 double/float64。

相似题目

题目 难度 考察点
416. 分割等和子集 中等 同样的倒序一维背包，但状态是布尔可达性而非概率
494. 目标和 中等 每件物品必选但符号二选一，要先做和差变换再背包
688. 骑士在棋盘上的概率 中等 概率在二维棋盘上按步数扩散，每步要均分到八个方向
518. 零钱兑换 II 中等 物品可无限次使用，内层必须改成正序才正确