Leetcode Problem 1230. Toss Strange Coins

Algorithm

1. Initialize a 1D array dp of size target + 1 with all elements set to 0.
2. Set dp[0] to 1, as the probability of getting 0 heads with 0 coins is 1.
3. Iterate over each coin i from 1 to n: a. For each possible number of heads j from target down to 1: i. Update dp[j] to dp[j - 1] * prob[i - 1] + dp[j] * (1 - prob[i - 1]). b. Update dp[0] to dp[0] * (1 - prob[i - 1]) to account for the probability of getting 0 heads with the current coin being tails.
4. After processing all coins, return dp[target] as the final probability of getting exactly target heads.