本文主要是介绍[算法][动态规划][腾讯面试手撕题]抛硬币问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
① 题目描述
有一些不规则的硬币。在这些硬币中， p i − 1 p_{i-1} pi−1表示第 i i i枚硬币正面朝上的概率( i i i从1起)。
请对每一枚硬币抛掷一次，然后返回正面朝上的硬币数等于 t a r g e t target target的概率。
② 问题求解
误区：这题容易被排列组合的想法先入为主，其实这是一个动态规划的问题。
1 动态方程
记 d p [ i ] [ j ] dp[i][j] dp[i][j]为抛第 i i i个硬币时恰好有 j j j个朝上的概率，则：
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ∗ ( 1 − p i − 1 ) + d p [ i − 1 ] [ j − 1 ] ∗ p i dp[i][j]=dp[i-1][j]*(1-p_{i-1}) +dp[i-1][j-1]*p_i dp[i][j]=dp[i−1][j]∗(1−pi−1)+dp[i−1][j−1]∗pi
反向迭代可以去除 i i i的维度，将空间优化为：
d p [ j ] = d p [ j ] ∗ ( 1 − p i − 1 ) + d p [ j − 1 ] ∗ p i dp[j]=dp[j]*(1-p_{i-1}) +dp[j-1]*p_i dp[j]=dp[j]∗(1−pi−1)+dp[j−1]∗pi
其中， d p [ j ] dp[j] dp[j]为恰有 j j j个硬币朝上的概率。
2 代码求解
"""
思路:动态规划 res[x]指的是恰好x个为正的概率@See 动态规划 https://leetcode-cn.com/tag/dynamic-programming/
样例输入:prob = [0.4], target = 1prob = [0.5,0.5,0.5,0.5,0.5], target = 0
样例输出:0.40000.03125
"""
from typing import Listclass Solution:def cal_probability(self, prob: List[float], target: int) -> float:res = [0 for _ in range(len(prob) + 1)]res[0] = 1.0for i in range(1, len(prob)+1):for j in range(min(i, target), -1, -1):# 恰好j个为正 = 上一轮更新中j个正面的情况下第i个恰好为反 + 已经j-1个正面的情况下第i个继续为正res[j] = (res[j] * (1 - prob[i - 1])) + ((res[j - 1] * prob[i - 1]) if j > 0 else 0)return res[target]
这篇关于[算法][动态规划][腾讯面试手撕题]抛硬币问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
