LeetCode 1230. 抛掷硬币

Categories:

题目描述
思路分析
1. 解法一：概率 DP（推荐）
相似题目

题目描述

✅ 1230. 抛掷硬币

思路分析

解法一：概率 DP（推荐）

核心思路：

设 dp[j] 表示当前抛掷到某个硬币时，恰好出现 j 个正面的概率。

对每个硬币概率 p，从大到小更新：dp[j] = dp[j] * (1 - p) + dp[j - 1] * p。

最终返回 dp[target]。

复杂度分析：

时间复杂度：O(n * target)，其中 n 为硬币数量。

空间复杂度：O(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 j = target; j >= 1; j--) {
                dp[j] = dp[j] * (1 - p) + dp[j - 1] * p;
            }
            dp[0] = dp[0] * (1 - 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 j := target; j >= 1; j-- {
            dp[j] = dp[j]*(1-p) + dp[j-1]*p
        }
        dp[0] = dp[0] * (1 - p)
    }

    return dp[target]
}

相似题目

题目	难度	考察点
518. 零钱兑换 II	中等	背包 DP
494. 目标和	中等	DP
1155. 掷骰子等于目标和的方法数	中等	DP
377. 组合总和 Ⅳ	中等	DP
688. “马”在棋盘上的概率	中等	概率 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/63557294