[算法][动态规划][腾讯面试手撕题]抛硬币（面试题）

阅读量：

① 题目描述

存在一些具有非标准特性的硬币。对于这些硬币而言， $p_{i-1}$ 代表第 $i$ 枚硬币在被抛掷时出现正面的概率（其中 $i$ 的起始值为1）。
要求对每枚硬币进行一次抛掷操作，并计算最终出现正面朝上的硬币数量恰好等于 $target$ 的概率值。

误区：此题常因受到排列组合思维的影响而误判，实际上应归类为动态规划类问题。

定义 $dp[i][j]$ 为在抛掷第 $i$ 个硬币时，恰好有 $j$ 个硬币朝上的概率，则：

$dp[i][j]=dp[i-1][j]*(1-p_{i-1}) +dp[i-1][j-1]*p_i$

通过采用反向迭代的方式，可以将与 $i$ 相关的维度进行消去，从而实现空间复杂度的优化，具体表达式如下：

$dp[j]=dp[j]*(1-p_{i-1}) +dp[j-1]*p_i$

在此表达式中， $dp[j]$ 表示恰好有 $j$ 个硬币处于朝上状态的概率。

复制代码

    """
    思路:
    动态规划 res[x]指的是恰好x个为正的概率
    @See 动态规划 https://leetcode-cn.com/tag/dynamic-programming/
    样例输入:
    prob = [0.4], target = 1

还没有任何评论哟~