难度: Medium
Submission
运行时间: 220 ms
内存: 0.0 MB
# class Solution:
# def probabilityOfHeads(self, prob: List[float], target: int) -> float:
# # for first n = 1 coins.
# dp = [0 for _ in range(target+1)]
# dp[0] = 1-prob[0]
# if target>0:
# dp[1] = prob[0]
# ndp = [0 for _ in range(target+1)]
# for n in range(2, len(prob)+1):
# p, q = prob[n-1], 1-prob[n-1]
# ndp[0] = dp[0]*q
# for t in range(1, target+1):
# ndp[t] = dp[t]*q+dp[t-1]*p
# dp, ndp = ndp, dp
# return dp[target]
class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
length = len(prob)-target+1
dp, comp = [1]*length, [1-p for p in prob]
for l in range(length-1):
dp[l+1] = dp[l] * comp[l]
for t in range(target):
dp[0] *= prob[0]
for l in range(1, length):
dp[l] = dp[l-1]*comp[l]+dp[l]*prob[l]
prob.pop(0), comp.pop(0)
return dp[-1]
# class Solution:
# def probabilityOfHeads(self, prob: List[float], target: int) -> float:
# length = len(prob) - target + 1
# dp, comp = [1] * length, [1-p for p in prob]
# for i in range(length-1):
# dp[i+1] = dp[i] * comp[i]
# for i in range(target):
# dp[0] *= prob[0]
# for j in range(1, length):
# dp[j] = dp[j-1] * comp[j] + dp[j] * prob[j]
# prob.pop(0), comp.pop(0)
# return dp[-1]
Explain
题解使用动态规划的方法计算恰好有'target'次正面朝上的概率。我们使用数组dp，其中dp[l]表示前l个硬币投掷后正面朝上次数为t的概率。初始时，我们设置dp[0]为1，表示没有硬币时恰好0次正面的概率为1。接下来，我们逐一考虑每个硬币，更新dp数组。对于每个硬币，我们先计算它反面朝上的概率存入comp数组。然后更新dp数组：对于每个索引l，如果我们不考虑新的硬币的影响，dp[l]会乘以comp[l]（因为硬币可能是反面朝上）。另外，由于新的硬币可能是正面朝上，我们还需要考虑dp[l-1]乘以prob[l]的情况。最后，我们更新dp数组，考虑下一个硬币。这一过程重复target次，最终dp数组的最后一个元素就是我们需要的结果。
时间复杂度: O((len(prob)-target+1)*target)
空间复杂度: O(len(prob)-target+1)
# class Solution:
# def probabilityOfHeads(self, prob: List[float], target: int) -> float:
length = len(prob)-target+1
dp, comp = [1]*length, [1-p for p in prob] # 初始化dp数组和comp数组
for l in range(length-1):
dp[l+1] = dp[l] * comp[l] # 更新dp数组不考虑新的硬币
for t in range(target):
dp[0] *= prob[0] # 第一个元素考虑新的硬币为正面的情况
for l in range(1, length):
dp[l] = dp[l-1]*comp[l]+dp[l]*prob[l] # 更新dp数组考虑新的硬币为正反两面的情况
prob.pop(0), comp.pop(0) # 移除已经考虑过的硬币
return dp[-1] # 返回目标正面朝上的概率
Explore
在动态规划中使用数组comp来存储每个硬币反面朝上的概率，主要是为了方便计算和更新dp数组。每次计算dp数组时，我们需要考虑当前硬币是正面还是反面的情况。使用comp数组存储反面概率，可以直接通过乘法更新不考虑新硬币影响的dp[l]的值（dp[l] *= comp[l]），这样可以加快计算速度，避免重复计算每个硬币的反面概率，提高算法效率。
初始化dp[0]为1的意义在于，它代表在没有投掷任何硬币时，恰好得到0次正面朝上的概率是100％，即确定事件。这是因为在没有任何投掷的情况下，出现0次正面是唯一可能的结果。如果初始化为其他值，将无法正确反映实际的概率情况，且后续的概率计算也会基于错误的初始值，导致最终结果不正确。
更新dp数组时，dp[l]的值更新为dp[l-1]*comp[l] + dp[l]*prob[l]，这是因为要考虑两种情况：一是前l-1个硬币已有l-1次正面，当前硬币是反面（概率为comp[l]）；二是前l个硬币已有l次正面，当前硬币是正面（概率为prob[l]）。这种更新逻辑通过考虑所有可能的情况，确保了概率计算的准确性，能够正确反映出在投掷l次硬币后，恰好有l次正面的概率。
每次循环后移除已经考虑过的硬币，确实会影响数组长度，因此在设计循环结构时需要注意。长度的减少意味着在后续的循环中，索引范围会相应减小。这种操作可以减少内存占用，同时确保每次循环处理的都是尚未考虑的硬币。循环结构需要根据调整后的数组长度进行控制，以避免索引越界的错误。