Formatted question description: https://leetcode.ca/all/1230.html

# 1230. Toss Strange Coins

## Level

Medium

## Description

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.

## Solution

Use dynamic programming. Let `length`

be the length of array `prob`

, and it can be seen that `length`

equals the number of coins.

Create a 2D array `dp`

with `length + 1`

rows and `target + 1`

columns. The element at `dp[i][j]`

stands for the probability that after the first `i`

coins are tossed, there are `j`

coins facing heads.

Obviously, if no coin is tossed, then definitely no coin faces heads, which has a probability 1, so `dp[0][0] = 1`

. Each time a coin is tossed, the number of coins facing heads either remains the same or increase by 1, depending on the current coin’s probability of facing heads. So the probability can be calculated. For the case `j`

equals 0, `dp[i][0]`

only depends on `prob[i - 1]`

and `dp[i - 1][0]`

. For other cases, `dp[i][j]`

depends on `prob[i - 1]`

, `dp[i - 1][j - 1]`

and `dp[i - 1][j]`

.

Finally, return `dp[length][target]`

for the result.

```
class Solution {
public double probabilityOfHeads(double[] prob, int target) {
int length = prob.length;
double[][] dp = new double[length + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= length; i++) {
double curProb = prob[i - 1];
dp[i][0] = dp[i - 1][0] * (1 - curProb);
for (int j = 1; j <= target; j++)
dp[i][j] = dp[i - 1][j - 1] * curProb + dp[i - 1][j] * (1 - curProb);
}
return dp[length][target];
}
}
```