【leetcode】1230.Toss Strange Coins

题目如下：

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:
Input: prob = [0.4], target = 1

Output: 0.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0

Output: 0.03125
Constraints:

1 <= prob.length <= 1000

0 <= prob[i] <= 1

0 <= target <= prob.length

Answers will be accepted as correct if they are within 10^-5 of the correct answer.

解题思路：动态规划。首先假设dp[i][j]为投完第i枚硬币后有j枚硬币朝上的概率。如果第i-1枚硬币投完后有j枚朝上，那么第i枚硬币就只能朝下；如果i-1枚硬币投完后有j-1枚朝上，那么第i枚硬币就只能朝上。很容易建立状态转移方程，dp[i][j] = dp[i-1][j-1] * prob[i] + dp[i-1][j] * (1 - prob[i])。

代码如下：

class Solution(object):

    def probabilityOfHeads(self, prob, target):

        """

        :type prob: List[float]

        :type target: int

        :rtype: float

        """

        dp = [[0]*(len(prob) + 1) for _ in prob]

        dp[0][0] = 1 - prob[0]

        dp[0][1] = prob[0]

        for i in range(1,len(prob)):

            for j in range(min(target+1,len(prob))):

                if j == 0:

                    dp[i][j] = float(dp[i-1][j]) * (1 - prob[i])

                    continue

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

        return dp[-1][target]

巴特西

【leetcode】1230.Toss Strange Coins

最新文章

热门文章