class Solution:

    def probabilityOfHeads(self, prob: List[float], target: int) -> float:

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

        dp[0][0] = 1.0

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

            for j in range(target+1)[::-1]:

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

                if j > 0:

                    dp[i][j] += dp[i-1][j-1] * prob[i-1]

        return dp[-1][-1]
            

class Solution:

    def probabilityOfHeads(self, prob: List[float], target: int) -> float:

        dp = [1] + [0] * target

        for p in prob:

            for i in range(target+1)[::-1]:

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

                if i > 0:

                    dp[i] += dp[i-1] * p

        return dp[-1]