Problem statement

https://binarysearch.com/problems/Multiple-Coin-Flips/

Solution

Equal to Leetcode 1230 Toss Strange Coins.

Complexity

It is O(nk) for time and space.

Code

class Solution:
    def solve(self, P, target):
        @lru_cache(None)
        
        def dp(i, j):
            if j < 0 or i - j < -1: return 0
            if i == -1: return 1
            return dp(i-1, j)*(1-P[i]) + dp(i-1, j-1)*P[i]
        
        return dp(len(P) - 1, target)

Remark

Notice, that there is also O(n log n) time complexity algorithm, using generating functions and fast polynoms multiplications.