【leetcode】1230.Toss Strange Coins

题目如下：

解题思路：动态规划。首先假设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]