5090. 抛掷硬币

有一些不规则的硬币。在这些硬币中，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 <= prob.length <= 1000
  • 0 <= prob[i] <= 1
  • 0 <= target<= prob.length
  • 如果答案与标准答案的误差在 10^-5 内，则被视为正确答案。

解题思路

解法1(超时)：

最开始我是想到用传统的排列组合方法来做的，因为我们在手算的时候也是这样，先从n个硬币中选target 个，让他们为正面，其他为反面，将概率相乘；最后将所有可能的组合相加起来。

但是这样做的话会超时。

解法2(动态规划)：

虽然咋一看这道题跟不是求最优化的，貌似跟动态规划风马牛不相及，但其实仔细一想我们在用解法1的时候 其实是有很多重复计算在里面的，这倒是跟动态规划有关了。

状态矩阵：dp[i][j]表示抛i个硬币，有j个向上的概率 状态转移方程：

    dp[i][j + 1] += dp[i - 1][j] * p
    dp[i][j] += dp[i - 1][j] * (1 - p)

解释：假设已知抛i - 1个硬币有j个向上的概率，那么在抛第i个硬币的时候，还是j个向上的概率就是第i 个硬币是向下的(1 - p)；那么j + 1个向上的概率就是第i个硬币是向上的(p)。 但是我们要知道抛i次有j次向上的组合是有多种的，而最后的概率是这些组合各自的概率的相加，因此 状态转移方程是 += 而不是 = 此外，我们初始化状态矩阵为全0，且dp[0][0]为1，因为抛0次只能有0个向上，概率为1

我们最后得到的状态矩阵是每一行的和都为1，因为每一行代表了抛i次，而抛i次的情况下共有0 ~ i个 向上的可能，这些概率加起来的和为1，而i+1以后的概率都为0. 也就是说我们最后得到的矩阵是一个下三角矩阵 (对角线以上的元素都为0)

# -*- coding: utf-8 -*-
# @Time         : 2019-10-20 16:07
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : tossCoin.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


class Solution:
    def probabilityOfHeads(self, prob, target: int) -> float:
        # 这里对0个向上的情况特殊考虑，因为这个case的计算简单，没必要通过dp，仅仅是为了加速
        if target == 0:
            ans = 1
            for p in prob:
                ans *= 1 - p
            return ans

        length = len(prob) + 1  # 由于我们第一维代表抛的次数，为了保持统一，将下标加一
        dp = [[0] * length for _ in range(length)]
        dp[0][0] = 1  # 抛0次的话只能有0个为正

        # 这里我们通过enumerate来遍历，顺便将下标的起始设为1，保持了状态矩阵各个元素的意义
        for i, p in enumerate(prob, 1):
            # 抛i次硬币可能会有0, 1, 2, ..., i - 1, i个向上，因此都需要计算
            for j in range(i):
                # 注意这里状态转移方程是 += ，不是 =
                dp[i][j] += dp[i - 1][j] * (1 - p)
                dp[i][j + 1] += dp[i - 1][j] * p
        return dp[-1][target]  # 最后抛n次，有target个向上的概率就是我们要的


def main():
    solution = Solution()
    prob = [0.2, 0.8, 0, 0.3, 0.5]
    target = 3
    print(solution.probabilityOfHeads(prob, target))


if __name__ == '__main__':
    main()